首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

HDU1045 Fire Net 暴力搜寻DFS

2012-07-19 
HDU1045 Fire Net暴力搜索DFS这题给出的图的行列范围较小,所以可以暴力来做。要解决的问题就是怎样方便的枚

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代码:


 

 

 

热点排行