题目意思：输入n，接下来为n行n列，X表示墙不能放置碉堡而且碉堡打不透,同行同列不能放两个碉堡（有x阻挡的除外）
问:最多可以建立多少个碉堡。
#include#include #include #include using namespace std;char str[20][20];struct node{ int x,y;} a[20][20];int maps[20][20];int used[20];int vis[20],x,y;int finds(int u){ for(int i=1; i<=y; i++) { if(!vis[i]&&maps[u][i]) { vis[i]=1; if(!used[i]||finds(used[i])) { used[i]=u; return 1; } } } return 0;}int main(){ int n; while(scanf("%d",&n),n) { for(int i=1; i<=n; i++) { scanf("%s",str[i]+1); } x=y=0; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(str[i][j]=='.')//对一排相邻的进行合并 { if(j==1||str[i][j-1]=='X') { x++; } a[i][j].x=x; } if(str[j][i]=='.')//对一列相邻的进行合并 { if(j==1||str[j-1][i]=='X') { y++; } a[j][i].y=y; } } } memset(maps,0,sizeof(maps)); for(int i=1; i<=n; i++)//建图。 { for(int j=1; j<=n; j++) { if(str[i][j]=='.') { int xx=a[i][j].x; int yy=a[i][j].y; maps[xx][yy]=1; } } } memset(used,0,sizeof(used)); int ans=0; for(int i=1; i<=x; i++) { memset(vis,0,sizeof(vis)); if(finds(i)) { ans++; } } printf("%d\n",ans); } return 0;}