HDOJ(HDU).1045 Fire Net (DFS)

2019-11-09 19:08:46

字體：大中小

供稿：網(wǎng)友

HDOJ(HDU).1045 Fire Net [從零開(kāi)始DFS(７)]

點(diǎn)我挑戰(zhàn)題目

從零開(kāi)始DFS HDOJ.1342 Lotto [從零開(kāi)始DFS(0)] — DFS思想與框架/雙重DFS HDOJ.1010 Tempter of the Bone [從零開(kāi)始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [從零開(kāi)始DFS(2)] —DFS四向搜索變種 HDOJ(HDU).1016 PRime Ring Problem (DFS) [從零開(kāi)始DFS(3)] —小結(jié)：做DFS題目的關(guān)注點(diǎn) HDOJ(HDU).1035 Robot Motion [從零開(kāi)始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開(kāi)始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開(kāi)始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開(kāi)始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

給出n * n 規(guī)模的地圖，其中.代表空白區(qū)域，X代表墻，求出在滿足以下規(guī)則的情況下，最多能建立多少座炮樓。規(guī)則： 1.假定炮樓可以四向發(fā)射炮彈，要求2個(gè)炮樓不能互相打到。（射程無(wú)限制） 2.墻可以攔截住炮彈。

相比于之前的dfs題目，本道題的限制要求頗為復(fù)雜，首先要求不能互相打到，直觀的感覺(jué)就是2個(gè)炮樓不能處在同一水平/豎直線上。其次要求墻可以攔截子彈，也就是說(shuō)2個(gè)炮樓可以在一條水平/豎直線上的要求就是當(dāng)且僅當(dāng)他們中間有墻分隔。不難從地圖中看出，每一個(gè)空白的格子均有可能建炮樓（題目中也說(shuō)了最大個(gè)數(shù)一定，但位置有可能有多解）。所以可以確定要遍歷整張地圖，即判斷每個(gè)格子是否滿足建炮樓的條件，會(huì)用到HDOJ(HDU).1241 Oil Deposits(DFS) [從零開(kāi)始DFS(5)] 討論過(guò)的雙重for循環(huán)遍歷整張地圖。回到dfs的核心：遞歸。這道題有沒(méi)有遞歸邊界呢？首先由于是對(duì)地圖進(jìn)行for循環(huán)遍歷，也就不會(huì)出現(xiàn)越界的情況，越界不會(huì)是遞歸邊界。其次這道題要求找出數(shù)量的最大值，于是在dfs中肯定會(huì)有更新最大值的部分。什么時(shí)候進(jìn)行遞歸呢？當(dāng)然就是滿足題目所說(shuō)的建立炮樓的規(guī)則的時(shí)候。推算到此，可見(jiàn)難點(diǎn)是如何實(shí)現(xiàn)這樣規(guī)則的檢查。

繼續(xù)看如何實(shí)現(xiàn)。按照規(guī)則，水平/豎直不能有其他的炮樓出現(xiàn)，不難想到，用for循環(huán)分別對(duì)上下左右四個(gè)方向檢查，如果遇到炮樓，則說(shuō)明這個(gè)位置不符合規(guī)則，返回false，或者是超越了地圖邊界，退出循環(huán)，再或者是遇到了墻退出當(dāng)前循環(huán)。為什么遇到墻就跳出循環(huán)了呢？也不難想到，就算墻后面是炮樓，也是符合規(guī)則的，所以干脆遇到墻就跳出循環(huán)。整個(gè)程序的架構(gòu)基本就是這樣，下面結(jié)合代碼，討論一些小問(wèn)題。

代碼總覽

/* 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函數(shù)完成初始化，地圖中的墻標(biāo)記為2（之后建立的炮樓標(biāo)記為1，沒(méi)有訪問(wèn)過(guò)就是0）；然后進(jìn)入dfs函數(shù)，dfs里面先是更新最大值的部分，然后是是雙重for循環(huán)。當(dāng)且僅當(dāng)此點(diǎn)滿足recheck時(shí)進(jìn)行遞歸操作，recheck就是上下左右檢查有沒(méi)有炮樓，當(dāng)然，如果這點(diǎn)本身就是墻的話，直接return false。如果滿足的話，把這點(diǎn)標(biāo)記為炮樓（visit[i][j] = 1），繼續(xù)遞歸調(diào)用dfs，當(dāng)然不要忘記無(wú)后效性（visit[i][j] = 0）。

上一篇：matlab cat函數(shù)

下一篇：【新人雜記】sleep 和 wait 的區(qū)別