原题链接：点击！
大致题意：白块表示可以放置炮台的位置——每个炮台可以攻击到上下左右的直线上的炮台（也就是说在它的上下左右直线上不可以再放置炮台，避免引起互相攻击），黑块表示隔离墙的位置——不可放置并且可以阻挡炮火；求对于一个最大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可以放置炮台，返回112 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‘){//一个方位上存在炮台，返回025 ????????????????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\n",ans);57 ????}58 59 ????return 0;60 }【HDU-1045,Fire Net-纯暴力简单DFS】
原文地址：https://www.cnblogs.com/zhazhaacmer/p/8504496.html