A - Fire Net（DFS）

题意：给 $n\times n$ 地图，问最多能放多少炮台，炮台不能互相攻击（有墙或者不在同一行或同一列）

思路：从左到右，从上到下将每个点做为起点开始搜，如果从某一个点开始搜，它之前的点是不用搜的，因为若

它之前有点可以作为炮台，说明这个点已经被搜过了。所以这种搜法是正确的。这里有个简化的技巧，用一维编号表示二维坐标以 $(0,0)$ 作为起点，记它的编号为 $0$ ,依次类推 $(n-1,n-1)$ 的编号为 $n\times n-1$

当前编号 $id$ 的坐标为 $(id/n,id\%n)$ .用两个数组分别标记行列，来维护整个地图即可。

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int N=505;
char mp[N][N];
int r[N],c[N],n,ans; 
void dfs(int id,int sum){
    if(id==n*n)//终止条件. 
    {
         if(sum>ans) ans=sum;
         return ;
    }
    int x=id/n,y=id%n;
    if(mp[x][y]=='X') r[x]=c[y]=0;
    if(mp[x][y]=='.'&&!r[x]&&!c[y]){
        mp[x][y]='Y';
        r[x]=c[y]=1;
        dfs(id+1,sum+1);
        mp[x][y]='.';//回溯 
        r[x]=c[y]=0;
    }
    dfs(id+1,sum);
}
int main(){
    while(~scanf("%d",&n)&&n)
    {
        ans=0;
        for(int i=0;i<n;i++)
            scanf("%s",mp[i]);
        dfs(0,0);
        printf("%d\n",ans);
    }
        return 0; 
}