【HDU-1045,Fire Net-纯暴力简单DFS】

大致题意：白块表示可以放置炮台的位置——每个炮台可以攻击到上下左右的直线上的炮台（也就是说在它的上下左右直线上不可以再放置炮台，避免引起互相攻击），黑块表示隔离墙的位置——不可放置并且可以阻挡炮火；求对于一个最大4*4的格子来说，最大的放置炮台的个数是多少。

简单分析：

简单的dfs（）;由于本题地图很小，不用考虑太多，尽情暴力即可。先把DFS枝干画出来，然后枝叶就用函数来具体实现。

AC代码：（附注释）

 1 #include <iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<stdlib.h>
 5 #include<stdio.h>
 6 using namespace std;
 7 char mp[5][5];
 8 int n,ans;
 9 int dir[4][2]={ {0,1},{0,-1},{1,0},{-1,0}  };
10 
11 int legal(int x,int y){//若点x,y可以放置炮台，返回1
12 
13     for(int i=0;i<4;i++){
14         for(int k=0;k<=3;k++){  //四个方位顶多走3步
15             int xx,yy;
16             xx=x+dir[i][0]*k;
17             yy=y+dir[i][1]*k;
18             if(!(xx>=0&&yy>=0&&xx<=n-1&&yy<=n-1)){  //越界,break,搜下一个方位！
19                 break;
20             }
21             if(mp[xx][yy]=='X'){  //一个方位上存在墙体
22                 break;
23             }
24             if(mp[xx][yy]=='D'){//一个方位上存在炮台，返回0
25                 return 0;
26             }
27         }
28     }
29     return 1;
30 
31 }
32 void dfs(int step)   //step表示已经完成的点数
33 {
34     ans=max(ans,step);
35     for(int i=0;i<n;i++){//每次搜索就是遍历一遍图，由于本题数据范围贼小，就不用考虑标记等
36         for(int j=0;j<n;j++){
37             if(mp[i][j]=='.'&&legal(i,j))//找到一处合法的‘.’
38             {
39                 mp[i][j]='D';//替换成D，简单清晰
40                 dfs(step+1);//dfs迭代
41                 mp[i][j]='.';//取消标记
42             }
43         }
44     }
45 
46 }
47 int main()
48 {
49     while(scanf("%d",&n),n!=0){
50         for(int i=0;i<n;i++){//读图
51             scanf("%s",mp[i]);
52         }
53         ans=0;
54 
55         dfs(0);  //开始搜索！
56         printf("%d
",ans);
57     }
58 
59     return 0;
60 }

View Code