题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=4554
题解：
如果没有硬石头的话，就是’*‘点对应的行列建边，然后跑最大匹配
硬石头什么作用？它可以让同一行或同一列存在不只一个炸弹，因此我们可以将一个硬石头的上下拆成两列，左右拆成两行，然后就可以用经典的做法来跑最大匹配了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 7 const int maxn = 55; 8 const int maxs = 2555; 9 int n, m; 10 11 char str[maxn][maxn]; 12 int _x[maxn][maxn], _y[maxn][maxn]; 13 int _r, _c; 14 vector<int> G[maxs]; 15 16 int lef[maxs], _t[maxs]; 17 bool match(int u) { 18 for (int j = 0; j < G[u].size(); j++) { 19 int v = G[u][j]; 20 if (!_t[v]) { 21 _t[v] = 1; 22 if (lef[v]==-1 || match(lef[v])) { 23 lef[v] = u; 24 return true; 25 } 26 } 27 } 28 return false; 29 } 30 31 int BM() { 32 memset(lef, -1, sizeof(lef)); 33 for (int i = 0; i < _r; i++) { 34 memset(_t, 0, sizeof(_t)); 35 match(i); 36 } 37 int ret = 0; 38 for (int i = 0; i < _c; i++) { 39 if (lef[i] != -1) ret++; 40 } 41 return ret; 42 } 43 44 void init() { 45 for (int i = 0; i < maxs; i++) G[i].clear(); 46 } 47 48 int main() { 49 while (scanf("%d%d", &n, &m) == 2 && n) { 50 init(); 51 for (int i = 0; i < n; i++) scanf("%s", str[i]); 52 _r = 0, _c = 0; 53 for (int i = 0; i < n; i++) { 54 for (int j = 0; j < m; j++) { 55 if (str[i][j] == '#') _r++; 56 else if (str[i][j] == '*') _x[i][j] = _r; 57 } 58 _r++; 59 } 60 for (int j = 0; j < m; j++) { 61 for (int i = 0; i < n; i++) { 62 if (str[i][j] == '#') _c++; 63 else if (str[i][j] == '*') _y[i][j] = _c; 64 } 65 _c++; 66 } 67 for (int i = 0; i < n; i++) { 68 for (int j = 0; j < m; j++) { 69 if (str[i][j] == '*') { 70 G[_x[i][j]].push_back(_y[i][j]); 71 } 72 } 73 } 74 printf("%d ", BM()); 75 } 76 return 0; 77 } 78 79 /* 80 4 4 81 #*** 82 *#** 83 **#* 84 xxx# 85 */