[ZOJ 1002] Fire Net (简单地图搜索)

浏览数：27 / 时间：2015年06月09日

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002

题目大意：

给你一个n*n的地图，地图上的空白部分可以放棋子，也有墙，问最多能放多少棋子使得棋子两两不会袭击？

棋子袭击当且仅当处在同一行或者同一列上并且中间没有墙的阻隔。

真是好久没写过搜索题了。。这道题都写了这么久！！

直接写dfs(x,y,now) 代表我现在站在x点，y点上，那么就只能产生两种状态，放棋子或者不放棋子。

然后写一个C(x,y)代表当前点能否放置棋子。

什么情况下可以放置棋子呢？

因为我们是从左上角到右下角放的嘛，所以说只需要看左边和上边有没有棋子了。

代码：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <cctype>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <iterator>
11 #include <functional>
12 #include <cmath>
13 #include <numeric>
14 using namespace std;
15 
16 typedef long long LL;
17 
18 int n;
19 char mp[10][10];
20 int maxn = 0;
21 
22 bool C(int x,int y){
23     bool hang = true,lie = true;
24     for(int i=x-1;i>=1;i--){
25         if( mp[i][y]==‘@‘ ) {
26             hang = false;
27             break;
28         }
29         if( mp[i][y]==‘X‘ ){
30             hang = true;
31             break;
32         }
33     }
34     for(int j=y-1;j>=1;j--){
35         if( mp[x][j]==‘@‘ ) {
36             lie = false;
37             break;
38         }
39         if( mp[x][j]==‘X‘ ){
40             lie = true;
41             break;
42         }
43     }
44     return hang&&lie;
45 }
46 
47 void dfs(int x,int y,int now){
48 //    printf("x=%d y=%d now=%d\n",x,y,now);
49     if( x==n&&y==n ){
50         if( mp[x][y]==‘.‘ && C(x,y) ) now = now+1;
51         maxn = max(maxn,now);
52         return;
53     }
54     if( mp[x][y]==‘.‘ && C(x,y) ){
55         mp[x][y] = ‘@‘;
56         if(y+1<=n) dfs(x,y+1,now+1);
57         else if(x+1<=n) dfs(x+1,1,now+1);
58         mp[x][y] = ‘.‘;
59     }
60     if(y+1<=n) dfs(x,y+1,now);
61     else if(x+1<=n) dfs(x+1,1,now);
62 }
63 
64 int main(){
65 //    freopen("output.txt","w",stdout);
66     while(scanf("%d",&n)!=EOF&&n){
67         if( n==0 ) break;
68         maxn = 0;
69         for(int i=1;i<=n;i++){
70             scanf("%s",mp[i]+1);
71         }
72         dfs(1,1,0);
73         printf("%d\n",maxn);
74     }
75     return 0;
76 }