题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4536
嗯，刚开始看到这道题的时候，想到dfs，如果能把每行和每列的按照障碍标号，然后当前标号作为一个标记，就可以dfs了，但是，当时没想到怎么映射，而且复杂度这样很高，因为这不是八皇后问题，复杂度就是阶乘而已。这个题的话那样就不好控制，要去搜每一个空白点才行，确保不会漏掉。
仔细想想，这个和一次消灭掉一行或者一列的那个题有点像。
这有个题解写的不错：
http://blog.csdn.net/crescent__moon/article/details/25074937
#include<bits/stdc++.h> using namespace std; const int MAXN=100+5; int n; char tu[MAXN][MAXN]; int hang[MAXN][MAXN],lie[MAXN][MAXN]; int match[MAXN*MAXN]; bool vis[MAXN*MAXN]; vector<int>head[MAXN*MAXN]; int cnt1,cnt2; void build() { cnt1=cnt2=0; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(tu[i][j]=='.') { if(tu[i][j]!=tu[i][j-1])hang[i][j]=++cnt1; else hang[i][j]=hang[i][j-1]; } } for(int j=1;j<=n;++j) for(int i=1;i<=n;++i) { if(tu[i][j]=='.') { if(tu[i][j]!=tu[i-1][j])lie[i][j]=++cnt2; else lie[i][j]=lie[i-1][j]; } } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) { if(tu[i][j]=='.') { head[hang[i][j]].push_back(lie[i][j]); } } } bool dfs(int u) { for(int i=0,l=head[u].size();i<l;++i) { int v=head[u][i]; if(!vis[v]) { vis[v]=1; if(match[v]==-1||dfs(match[v])) { match[v]=u; return 1; } } } return 0; } int main() { while(~scanf("%d",&n)) { memset(tu,0,sizeof(tu)); for(int i=1;i<=n;++i)scanf("%s",tu[i]+1); build(); int ans=0; fill(match+1,match+cnt2+1,-1); for(int i=1;i<=cnt1;++i) { fill(vis+1,vis+1+cnt2,0); if(dfs(i))ans++; } printf("%d\n",ans); for(int i=1;i<=cnt1;++i)head[i].clear(); } }