HDU 1045 Fire Net (BFS)

 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 
 5 int n,res;
 6 char map[5][5];
 7 
 8 bool judge(int i,int j)
 9 {
10     int x,y;
11     for(x=i-1;x>=0;x--)
12     {
13         if(map[x][j]==‘X‘)
14             break;
15         if(map[x][j]==‘@‘)//@表示炮台
16             return false;
17     }
18     //for(x=i+1;x<n;x++)
19     //{
20     //    if(map[x][j]==‘X‘)
21     //        break;
22     //    if(map[x][j]==‘@‘)//@表示炮台
23     //        return false;
24     //}
25     //这步没什么必要...因为是从前往后搜索的
26     for(y=j-1;y>=0;y--)
27     {
28         if(map[i][y]==‘X‘)
29             break;
30         if(map[i][y]==‘@‘)//@表示炮台
31             return false;
32     }
33     //for(y=j+1;y<n;y++)
34     //{
35     //    if(map[i][y]==‘X‘)
36     //        break;
37     //    if(map[i][y]==‘@‘)//@表示炮台
38     //        return false;
39     //}
40     //没必要同上
41     return true;
42 }
43 
44 void dfs(int k,int t)//k from 0 to n*n-1 代表每一个位置
45 {
46     if(k==n*n)
47     {
48         if(t>res)res=t;
49         return ;
50     }
51     else
52     {
53         int i,j;
54         i=k/n;
55         j=k%n;
56         if(map[i][j]==‘.‘&&judge(i,j))
57         {
58             map[i][j]=‘@‘;
59             dfs(k+1,t+1);
60             map[i][j]=‘.‘;
61         }
62         dfs(k+1,t);//不能加else，因为表示两种情况，一种是不符合情况，第二种是情况后的回溯
63     }
64 }
65 
66 int main()
67 {
68     while(cin>>n&&n)
69     {
70         int i,j;
71         for(i=0;i<n;i++)
72             for(j=0;j<n;j++)
73                 cin>>map[i][j];
74         res=0;
75         dfs(0,0);
76         cout<<res<<endl;
77     }
78     return 0;
79 }