HDOJ(HDU).1035 Robot Motion (DFS)

2019-11-11 04:21:11

字體：大中小

來源：轉載

供稿：網友

HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]

點我挑戰題目

從零開始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 * m, 給出入口坐標(0,y),遵循以下規則，求解機器人能否走出地圖。若能，輸出走出地圖所需要的步數，若不能，輸出進入循環前走的步數和循環的步數。

規則：若當前格子為N，則只能向上走，若為S向下走，E向右走，W向左走。

我第一感覺是模擬題，因為對于每個格子狀態是唯一的，只有1組解：要么能走出去，要么不能。分別求出步數就行了，但感覺dfs能做，決定還是按照dfs的方法試一試。

分析一波：遞歸邊界就是機器人走出了地圖或者是機器人走回到了走過的地方（吃回頭草了），即可判定輸出了。那么需要記錄的東西就是當前走的步數，和循環的步數。當前走的步數好說，遞歸傳參+1就行了，循環的步數想想也不難：當下一步就要吃回頭草的時候，兩個狀態的步數之差就是循環的步數。與先前的雙重搜索，四向搜索不同，dfs中要判斷這個格子的字符是什么，然后決定如何走下一步。

上代碼。

代碼總覽

/* Title:HDOJ.1035 Author:pengwill Date:2017-2-6*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n,m,y,loop,step,beloop;char mp[11][11];int visit[11][11];bool judge = false;bool check(int x, int y){ if(x<0||x>=n||y<0||y>=m){ judge = true ;return false;} else return true;}void dfs(int x, int y, int s){ if(!check(x,y)) return; step = s; if(!judge){ if(!visit[x][y]){ visit[x][y] = s; if(mp[x][y] == 'N') dfs(x-1,y,s+1); else if(mp[x][y] == 'S') dfs(x+1,y,s+1); else if(mp[x][y] == 'E') dfs(x,y+1,s+1); else if(mp[x][y] == 'W') dfs(x,y-1,s+1); }else{ beloop = visit[x][y]-1; loop = s - visit[x][y] ; } }}int main(){ // 難點如何記步 //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)&&n){ scanf("%d",&y);y--; for(int i = 0;i<n;++i) scanf("%s",mp[i]); judge = false; memset(visit,0,sizeof(visit)); dfs(0,y,1); if(judge) printf("%d step(s) to exit/n",step); else printf("%d step(s) before a loop of %d step(s)/n",beloop,loop); } return 0;}

首先有3個全局變量保存著結果，分別是step,loop,beloop，分別保存著走出地圖用的步數，循環的步數，在循環之前的步數。 main函數完成初始化，check函數檢查是否走出地圖，若走出地圖則judge置為true并且終止遞歸。每一步把當前的步數保存在visit[x][y]中，并且根據visit[x][y]是否為0判斷是否吃了“回頭草”。最后別忘了及時更新loop和beloop。

應該來說是一道簡單的dfs應用題。

從零開始DFS: HDOJ.1342 Lotto [從零開始DFS(0)] HDOJ.1010 Tempter of the Bone [從零開始DFS(1)] HDOJ(HDU).1015 Safecracker [從零開始DFS(2)] HDOJ(HDU).1015 Safecracker [從零開始DFS(3)]

上一篇：夕拾算法進階篇：15)最長公共子序列(動態規劃DP)

下一篇：從JVM看性能分析與設計