HDOJ(HDU).1045 Fire Net (DFS)

2019-11-10 17:10:17

字体：大中小

来源：转载

供稿：网友

HDOJ(HDU).1045 Fire Net [从零开始DFS(７)]

点我挑战题目

从零开始DFS HDOJ.1342 Lotto [从零开始DFS(0)] — DFS思想与框架/双重DFS HDOJ.1010 Tempter of the Bone [从零开始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [从零开始DFS(2)] —DFS四向搜索变种 HDOJ(HDU).1016 PRime Ring Problem (DFS) [从零开始DFS(3)] —小结：做DFS题目的关注点 HDOJ(HDU).1035 Robot Motion [从零开始DFS(4)]—DFS题目练习 HDOJ(HDU).1241 Oil Deposits(DFS) [从零开始DFS(5)] —DFS八向搜索/双重for循环遍历 HDOJ(HDU).1258 Sum It Up (DFS) [从零开始DFS(6)] —DFS双重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [从零开始DFS(７)]—DFS练习/check函数的思想

题意分析

给出n * n 规模的地图，其中.代表空白区域，X代表墙，求出在满足以下规则的情况下，最多能建立多少座炮楼。规则： 1.假定炮楼可以四向发射炮弹，要求2个炮楼不能互相打到。（射程无限制） 2.墙可以拦截住炮弹。

相比于之前的dfs题目，本道题的限制要求颇为复杂，首先要求不能互相打到，直观的感觉就是2个炮楼不能处在同一水平/竖直线上。其次要求墙可以拦截子弹，也就是说2个炮楼可以在一条水平/竖直线上的要求就是当且仅当他们中间有墙分隔。不难从地图中看出，每一个空白的格子均有可能建炮楼（题目中也说了最大个数一定，但位置有可能有多解）。所以可以确定要遍历整张地图，即判断每个格子是否满足建炮楼的条件，会用到HDOJ(HDU).1241 Oil Deposits(DFS) [从零开始DFS(5)] 讨论过的双重for循环遍历整张地图。回到dfs的核心：递归。这道题有没有递归边界呢？首先由于是对地图进行for循环遍历，也就不会出现越界的情况，越界不会是递归边界。其次这道题要求找出数量的最大值，于是在dfs中肯定会有更新最大值的部分。什么时候进行递归呢？当然就是满足题目所说的建立炮楼的规则的时候。推算到此，可见难点是如何实现这样规则的检查。

继续看如何实现。按照规则，水平/竖直不能有其他的炮楼出现，不难想到，用for循环分别对上下左右四个方向检查，如果遇到炮楼，则说明这个位置不符合规则，返回false，或者是超越了地图边界，退出循环，再或者是遇到了墙退出当前循环。为什么遇到墙就跳出循环了呢？也不难想到，就算墙后面是炮楼，也是符合规则的，所以干脆遇到墙就跳出循环。整个程序的架构基本就是这样，下面结合代码，讨论一些小问题。

代码总览

/* Title:HDOJ.1045 Author:pengwill Date:2017-2-9*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char mp[5][5];int visit[5][5];int n,ans;void init(){ ans = 0; memset(visit,0,sizeof(visit)); for(int i = 0 ;i< n;++i) for(int j = 0;j <n; ++j){ if(mp[i][j] == 'X') visit[i][j] = 2; }}bool check(int x, int y){ if(x<0 || x>=n || y<0 || y>=n) return false; else return true;}bool recheck(int x, int y){ if(visit[x][y] == 2 ) return false; //right for(int i = x;check(i,y);++i){ if(visit[i][y] == 2) break; if(visit[i][y] == 1) return false; } //left for(int i = x;check(i,y);--i){ if(visit[i][y] == 2) break; if(visit[i][y] == 1) return false; } //up for(int i = y;check(x,i);++i){ if(visit[x][i] == 2) break; if(visit[x][i] == 1) return false; } //down for(int i = y;check(x,i);--i){ if(visit[x][i] == 2) break; if(visit[x][i] == 1) return false; } return true;}void dfs(int num){ if(num>ans) ans = num; for(int i = 0;i<n;++i){ for(int j = 0;j<n;++j){ if(recheck(i,j)){ visit[i][j] = 1; dfs(num+1); visit[i][j] = 0; } } }}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d",&n)&&n){ for(int i = 0;i<n;++i) scanf("%s",mp[i]); init(); dfs(0); printf("%d/n",ans); } return 0;}

init函数完成初始化，地图中的墙标记为2（之后建立的炮楼标记为1，没有访问过就是0）；然后进入dfs函数，dfs里面先是更新最大值的部分，然后是是双重for循环。当且仅当此点满足recheck时进行递归操作，recheck就是上下左右检查有没有炮楼，当然，如果这点本身就是墙的话，直接return false。如果满足的话，把这点标记为炮楼（visit[i][j] = 1），继续递归调用dfs，当然不要忘记无后效性（visit[i][j] = 0）。

上一篇：稳定婚姻问题（The Stable Marriage Problem）

下一篇：PAT-B 1008. 数组元素循环右移问题 (20)