数据范围比较小，直接暴力单点递归即可。
#include<bits/stdc++.h> using namespace std; char G[100][100]; int vis[100],ans=0,n,vis1[100]; void dfs(int x,int y,int cnt) { if(x==n&&y==0) { ans=max(ans,cnt); return ; } if(G[x][y]=='X') { vis[x]=0; vis1[y]=0; } if(!vis[x]&&!vis1[y]&&G[x][y]=='.') { cnt++; vis[x]=1; vis1[y]=1; if(y==n-1) dfs(x+1,0,cnt); else dfs(x,y+1,cnt); cnt--; vis[x]=0; vis1[y]=0; } if(y==n-1) dfs(x+1,0,cnt); else dfs(x,y+1,cnt); } int main() { while(scanf("%d",&n),n) { memset(vis,0,sizeof(vis)); memset(vis1,0,sizeof(vis1)); for(int i=0;i<n;i++) scanf("%s",G[i]); ans=0; dfs(0,0,0); printf("%d\n",ans); } }
