这题给出的图的行列范围较小,所以可以暴力来做。
要解决的问题就是怎样方便的枚举完所有可能的情况,并且得到放置blockhouse的最大值。
这要在dfs上下功夫了。
代码中的dfs原型为dfs(int i,int num)。其中 i 为记录该次搜索已经到达那一个点了(i=1、2、...、n*n ,
表示从左到右、从上到下给每个点编号)。num是用来记录当前搜索已经添加的blockhouse数目,另
一个功能就是当本次搜索结束,也就是i==n*n时,和全局变量maxNum比较并保留最大值放在maxNum
中。这样当所有情况都搜完后,maxNum要求值了。
还有一些小细节:
1、canPlace(int row,int col) 用来判断当前点 (row,col) 所在行列是否已经放置可以攻击到该点的blockhouse。
2、如果当前点可以放置blockhouse则标记为 'o' 表示已放。当然也可以开一个二维数组visit[][]来标记。方法
不一。
AC代码:
#include<iostream> using namespace std; const int MAX=4; char map[MAX][MAX]; int n,maxNum; void storeMap() //存图 { for(int i=0;i<n;i++) cin>>map[i]; } bool canPlace(int row,int col) //判断是否可以放置 { //在遇到墙之前同行或同列上已放置,则不能再放 int i; for(i=col-1;i>=0;i--) { if(map[row][i]=='o') return false; if(map[row][i]=='X') break; } for(i=row-1;i>=0;i--) { if(map[i][col]=='o') return false; if(map[i][col]=='X') break; } return true; } void dfs(int i,int num) //深搜,i代表已经搜索到的点,num代表该次搜索可以放得最多blockhouse { //搜索完所有可能情况,每点'.'都会作为起点搜索一遍 int row,col; if(i==n*n) { if(num>maxNum) maxNum=num; //比较每遍搜索结果,保留当前最大值 return; } else { row=i/n; //从左到右,从上到下依次给每个点编号,1、2、...、n*n col=i%n; //这是在取当前点所在图的行和列 if(map[row][col]=='.' && canPlace(row,col)) { map[row][col]='o'; dfs(i+1,num+1); map[row][col]='.'; } dfs(i+1,num); } } int main() { while(cin>>n,n) { storeMap(); maxNum=0; dfs(0,0); cout<<maxNum<<endl; } return 0; }