A - Fire Net（DFS）
A - Fire Net（DFS）
题意：给地图，问最多能放多少炮台，炮台不能互相攻击（有墙或者不在同一行或同一列）
思路：从左到右，从上到下将每个点做为起点开始搜，如果从某一个点开始搜，它之前的点是不用搜的，因为若
它之前有点可以作为炮台，说明这个点已经被搜过了。所以这种搜法是正确的。这里有个简化的技巧，用一维编号表示二维坐标 以作为起点，记它的编号为
,依次类推
的编号为
当前编号的坐标为
.用两个数组分别标记行列，来维护整个地图即可。
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;
} 
查看3道真题和解析