1002 Fire Net

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

用递归实现各种情况的枚举，可以看做是考察DPS的简单实现。

 1 #include <stdio.h>
 2 
 3 int n,max,count,target[4][4];
 4 
 5 int place(int x,int y){
 6     int i;
 7     for(i=y;i>=0;i--){
 8         if(target[x][i]>0)
 9             return 0;
10         if(target[x][i]<0)
11             break;
12     }
13     for(i=y;i<n;i++){
14         if(target[x][i]>0)
15             return 0;
16         if(target[x][i]<0)
17             break;
18     }
19     for(i=x;i>=0;i--){
20         if(target[i][y]>0)
21             return 0;
22         if(target[i][y]<0)
23             break;
24     }
25     for(i=x;i<n;i++){
26         if(target[i][y]>0)
27             return 0;
28         if(target[i][y]<0)
29             break;
30     }
31     return 1;
32 }
33 
34 void DFS(){
35     int i,j;
36     if(count>max)
37         max=count;
38     for(i=0;i<n;i++){
39         for(j=0;j<n;j++){
40             if(!target[i][j]&&place(i,j)){
41                 target[i][j]=1;
42                 count++;
43                 DFS();
44                 count--;
45                 target[i][j]=0;
46             }
47         }
48     }
49 }
50 
51 int main(){
52     int i,j;
53     char c;
54     while(1){
55         scanf("%d",&n);
56         if(n==0)
57             break;
58         max=count=0;
59         for(i=0;i<n;i++){
60             getchar();
61             for(j=0;j<n;j++){
62                 scanf("%c",&c);
63                 target[i][j]=(c==‘X‘?-1:0);
64             }
65         }
66         DFS();
67         printf("%d\n",max);
68     }
69     return 0;
70 }