題意：

給出一個圖，其中有 . 和 X 兩種，. 為通路，X表示墻，在.中放炸彈，然后炸彈不能穿過墻且不能互相炸到，問你最多在圖中可以放多少個炸彈？

思路：

因為數據很弱，所以搜索也可以過。還有個更好的方法，二分圖最大匹配。

難在建圖，把每一行中的可以放一個炸彈的一塊區域標記為同一個數字，列也一樣。

這樣每個點就有一個行標記值和列標記值，然后按照這兩個數字進行二分匹配。最大匹配即為最多能放的炸彈數目。

最大匹配代碼：

#include<bits/stdc++.h>using namespace std;const int maxn = 55;vector<int> e[maxn];int n, rowNum, colNum, row[maxn][maxn], col[maxn][maxn], match[maxn], vis[maxn];char pic[maxn][maxn];bool Hungary(int x){    for(int i = 0; i < e[x].size(); i++)    {        int to = e[x][i];        if(!vis[to])        {            vis[to] = 1;            if(!match[to] || Hungary(match[to]))            {                match[to] = x;                return true;            }        }    }    return false;}int main(void){    while(cin >> n, n)    {        memset(row, 0, sizeof(row));        memset(col, 0, sizeof(col));        memset(match, 0, sizeof(match));        for(int i = 0; i < maxn; i++)            e[i].clear();        for(int i = 0; i < n; i++)            for(int j = 0; j < n; j++)                scanf(" %c", &pic[i][j]);        //        rowNum = 1, colNum = 1;        for(int i = 0; i < n; i++)            for(int j = 0; j < n; j++)            {                if(pic[i][j] == '.' && !row[i][j])                {                    for(int k = j; k < n && pic[i][k] == '.'; k++)                        row[i][k] = rowNum;                    rowNum++;                }                if(pic[i][j] == '.' && !col[i][j])                {                    for(int k = i; k < n && pic[k][j] == '.'; k++)                        col[k][j] = colNum;                    colNum++;                }            }        //每個點的行標記值和列標記值構成關系        for(int i = 0; i < n; i++)            for(int j = 0; j < n; j++)                if(pic[i][j] == '.')                    e[row[i][j]].push_back(col[i][j]);        int ans = 0;        for(int i = 1; i < rowNum; i++)        {            memset(vis, 0, sizeof(vis));            if(Hungary(i)) ans++;        }        PRintf("%d/n", ans);    }    return 0;}
搜索代碼：
#include<iostream>#include<cstdio>using namespace std;const int maxn = 10;char pic[maxn][maxn];int n, ans;bool judge(int x, int y){    if(pic[x][y] != '.') return false;    for(int i = y-1; i >= 0; i--)    {        if(pic[x][i] == 'X') break;        if(pic[x][i] == 0) return false;    }    for(int i = x-1; i >= 0; i--)    {        if(pic[i][y] == 'X') break;        if(pic[i][y] == 0) return false;    }    return true;}void dfs(int x, int y, int num){    if(x == n) { ans = max(ans, num); return ;}    if(y == n) { dfs(x+1, 0, num); return ;}    for(int i = y; i < n; i++)        if(judge(x, i))        {            pic[x][i] = 0;            dfs(x, i+1, num+1);            pic[x][i] = '.';        }    dfs(x+1, 0, num);}int main(void){    while(cin >> n, n)    {        for(int i = 0; i < n; i++)            scanf(" %s", pic[i]);        ans = 0;        dfs(0, 0, 0);        printf("%d/n", ans);    }    return 0;}