Posted on 2007-04-16 20:47
oyjpart 阅读(959)
评论(0) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
Problem Statement
|
| |
You have been given a rows-by-cols chessboard, with a list of squares cut out. The list of cutouts will be given in a String[] cutouts. Each element of cutouts is a comma-delimited lists of coords. Each coord has the form (quotes for clarity) "r c". If coord "r c" appears in an element of cutouts, it means that the square at row r column c (0-based) has been removed from the chessboard. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Your method will return an int that will be the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack. |
|
Constraints
|
| - |
rows will be between 1 and 300 inclusive. |
| - |
cols will be between 1 and 300 inclusive. |
| - |
cutouts will contain between 0 and 50 elements inclusive. |
| - |
Each element of cutouts will contain between 3 and 50 characters inclusive. |
| - |
Each element of cutouts will be a comma delimited list of coords. Each coord will be of the form "r c", where
- r and c are integers, with no extra leading zeros,
- r is between 0 and rows-1 inclusive,
- and c is between 0 and cols-1 inclusive.
|
| - |
Each element of cutouts will not contain leading or trailing spaces. |
Examples
| 1) |
|
| |
2
|
2
|
{"0 0","0 1","1 1","1 0"}
|
|
Returns: 0
|
|
|
| 2) |
|
| |
3
|
3
|
{"0 0","1 0","1 1","2 0","2 1","2 2"}
|
|
Returns: 2
|
|
|
看到这个题目有什么想法？
8皇后问题相信是大家入门搜索或其他算法的经典教材了 如果被砍掉部分格子呢？
看到row和col分别是300的时候相信想搜索的朋友们心里可能要嘀咕一下了
如果这样分析一下：
由于在放置rook的时候要求这一行还有这一列一定只有这一个元素（注意是rook 不是queen 不要求斜行）
也就是说一个rook可以唯一的决定一行和一列
那么。。
这个rook似乎可以看成是某一行和某一列的一条边
如果把rows作为一个集合 cols作为一个集合 把不是cut out的点作为row和col的连接
于是就转化成了：二分图匹配
按照最短路的增广分析 时间复杂度不会超过o(n^3) 满足题目要求
比如一个3*3的棋盘 被cut out掉了(0,0) (1,2) (2,2) 3个格子
row集合 0，1，2
col集合 0，1，2
可连接的边为(0, 1), (0,2), (1, 0), (1,1), (2,0),(2,1)
执行最大匹配 将会得到如下结果
(0,2) (1,0), (2,1)
满足题意