Place the Robots
Robert is a famous engineer. One day he was given a task by his boss. The background of the task was the following: Given a map consisting of square blocks. There were three kinds of blocks: Wall, Grass, and Empty. His boss wanted to place as many robots as possible in the map. Each robot held a laser weapon which could shoot to four directions (north, east, south, west) simultaneously. A robot had to stay at the block where it was initially placed all the time and to keep firing all the time. The laser beams certainly could pass the grid of Grass, but could not pass the grid of Wall. A robot could only be placed in an Empty block. Surely the boss would not want to see one robot hurting another. In other words, two robots must not be placed in one line (horizontally or vertically) unless there is a Wall between them.
Now that you are such a smart programmer and one of Robert's best friends, He is asking you to help him solving this problem. That is, given the description of a map, compute the maximum number of robots that can be placed in the map.
Input
The first line contains an integer T (<= 11) which is the number of test cases.
For each test case, the first line contains two integers m and n (1<= m, n <=50) which are the row and column sizes of the map. Then m lines follow, each contains n characters of '#', '*', or 'o' which represent Wall, Grass, and Empty, respectively.
Output
For each test case, first output the case number in one line, in the format: "Case :id" where id is the test case number, counting from 1. In the second line just output the maximum number of robots that can be placed in that map.
Sample Input
2
4 4
o***
*###
oo#o
***o
4 4
#ooo
o#oo
oo#o
***#
Sample Output
Case :1
3
Case :2
5
Author: XU, Luchuan
Source: ZOJ Monthly, October 2003
题目类型：二分图最大匹配
算法分析：由于点的数量比较多，直接建图会TLE，所以需要进行一定的转化。这里先将原来的图进行一个等效：分别将水平方向上冲突的点看做是在一个块中，竖直方向上冲突的的点看做是在一个块中，易知每个块中最多只能选择一个点。然后将水平方向和竖直方向重合的点之间连一条边，这样就将原来的图转化成一个等效的二分图。之后就是在其上跑一个最大匹配
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
/************************************************* Author :supermaker Created Time :2016/1/19 15:19:21 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 50 + 1; int xs[maxn][maxn], ys[maxn][maxn]; bool vis[maxn*maxn], g[maxn*maxn][maxn*maxn]; int cx[maxn*maxn], cy[maxn*maxn], cxlen, cylen; char gg[maxn][maxn]; int row, col; int dfs (int u) { for (int v = 1; v <= cylen; v++) if (g[u][v] && !vis[v]) { vis[v] = true; if (cy[v] == -1 || dfs (cy[v])) { cy[v] = u; cx[u] = v; return 1; } } return 0; } int maxmatch () { int res = 0; memset (cx, -1, sizeof (cx)); memset (cy, -1, sizeof (cy)); for (int i = 1; i <= cxlen; i++) if (cx[i] == -1) { memset (vis, false, sizeof (vis)); res += dfs (i); } return res; } void PP () { memset (xs, 0, sizeof (xs)); memset (ys, 0, sizeof (ys)); memset (g, false, sizeof (g)); cxlen = 0; for (int i = 1; i <= row; i++) { bool is_new = true; for (int j = 1; j <= col; j++) { if (gg[i][j] == 'o') { if (is_new) cxlen++, is_new = false; xs[i][j] = cxlen; } else if (gg[i][j] == '#') is_new = true; } } cylen = 0; for (int i = 1; i <= col; i++) { bool is_new = true; for (int j = 1; j <= row; j++) { if (gg[j][i] == 'o') { if (is_new) cylen++, is_new = false; ys[j][i] = cylen; } else if (gg[j][i] == '#') is_new = true; } } for (int i = 1; i <= row; i++) for (int j = 1; j <= col; j++) if (xs[i][j]) g[xs[i][j]][ys[i][j]] = true; } int main() { //CFF; //CPPFF; int t, flag = 1; scanf ("%d", &t); while (t--) { printf ("Case :%d\n", flag++); scanf ("%d%d", &row, &col); for (int i = 1; i <= row; i++) for (int j = 1; j <= col; j++) scanf (" %c", &gg[i][j]); PP (); printf ("%d\n", maxmatch ()); } return 0; } |
- « 上一篇：hdu4417
- poj1466：下一篇 »