HDU1045 Fire Net 暴力搜索DFS
这题给出的图的行列范围较小,所以可以暴力来做。
要解决的问题就是怎样方便的枚举完所有可能的情况,并且得到放置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代码: