ZOJ-1002:Fire Net (DFS)

搜索

题面链接

• 题意

  已知一个n*n的矩阵，想在其中放置炮弹，求最多能放多少个。'.'表示可以放炮的位置。'X'表示是墙壁不能放炮。放炮的规则是炮弹不能互相打到。炮弹可以打他所在的一行和那一列。但是墙壁是打不穿的。

• 样例

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
Sample output:
5
1
5
2
4

• 分析

注意变量的定义！！！！出了好几次这样的错误了！要用再定义！不要全部定义在全局里！！会出问题的！！！还有BFS和DFS都是判断该点是否符合操作的条件。但是就算满足条件你也可以选择不放。放和不放是一种选择！！

• 代码

#include<bits/stdc++.h>
using namespace std;
int i,j,n,ans;
int cnt,num;
char mp[11][11];
//'.'表示平地可以放炮
//'#'表示已经放了炮
//'X'表示墙不能放炮
int check(int x,int y)//判断x,y位置是否可以放炮
{
    for(i=x-1;i>=0;i--)
    {
        if(mp[i][y]=='#')//这一行已经有炮了
            return 0;
        if(mp[i][y]=='X')//有墙
            break;
    }
    for(i=y-1;i>=0;i--)
    {
        if(mp[x][i]=='#')//这一列已经有炮了
            return 0;
        if(mp[x][i]=='X')
            break;
    }
    return 1;
}
void DFS(int num,int cnt)//num:遍历的点的个数，cnt：放的炮的个数
{
   int x,y;
   if(num==n*n)//边界条件
   {
       if(ans<cnt)
       {
           ans=cnt;
       }  
       return;
   }
   else
   {
       x=num/n;//行
       y=num%n;//列
       if((mp[x][y]=='.')&&(check(x,y)==1))//该点是平地，并且周围条件可放炮
       {
           mp[x][y]='#';//更新这一点为放炮的状态
           DFS(num+1,cnt+1);//递归进入下一个状态
           mp[x][y]='.';//回溯
       }
       DFS(num+1,cnt);//不管这个点合不合适，我都可以选择不放
   }
}
int main()
{
    while(scanf("%d",&n)&&n!=0)
    {
        for(i=0;i<n;i++)
            scanf("%s",&mp[i]);
        ans=0;
        DFS(0,0);
        printf("%d\n",ans);
    }
    return 0;
}