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)