HDOJ(HDU).1035 Robot Motion (DFS)

2019-11-11 05:48:25

字體：大中小

供稿：網(wǎng)友

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

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

從零開始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)] —小結(jié)：做DFS題目的關(guān)注點(diǎn) HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

給出地圖規(guī)模n * m, 給出入口坐標(biāo)(0,y),遵循以下規(guī)則，求解機(jī)器人能否走出地圖。若能，輸出走出地圖所需要的步數(shù)，若不能，輸出進(jìn)入循環(huán)前走的步數(shù)和循環(huán)的步數(shù)。

規(guī)則：若當(dāng)前格子為N，則只能向上走，若為S向下走，E向右走，W向左走。

我第一感覺是模擬題，因?yàn)閷τ诿總€格子狀態(tài)是唯一的，只有1組解：要么能走出去，要么不能。分別求出步數(shù)就行了，但感覺dfs能做，決定還是按照dfs的方法試一試。

分析一波：遞歸邊界就是機(jī)器人走出了地圖或者是機(jī)器人走回到了走過的地方（吃回頭草了），即可判定輸出了。那么需要記錄的東西就是當(dāng)前走的步數(shù)，和循環(huán)的步數(shù)。當(dāng)前走的步數(shù)好說，遞歸傳參+1就行了，循環(huán)的步數(shù)想想也不難：當(dāng)下一步就要吃回頭草的時候，兩個狀態(tài)的步數(shù)之差就是循環(huán)的步數(shù)。與先前的雙重搜索，四向搜索不同，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(){ // 難點(diǎn)如何記步 //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個全局變量保存著結(jié)果，分別是step,loop,beloop，分別保存著走出地圖用的步數(shù)，循環(huán)的步數(shù)，在循環(huán)之前的步數(shù)。 main函數(shù)完成初始化，check函數(shù)檢查是否走出地圖，若走出地圖則judge置為true并且終止遞歸。每一步把當(dāng)前的步數(shù)保存在visit[x][y]中，并且根據(jù)visit[x][y]是否為0判斷是否吃了“回頭草”。最后別忘了及時更新loop和beloop。

應(yīng)該來說是一道簡單的dfs應(yīng)用題。

從零開始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)]

上一篇：JVM內(nèi)存的那些事

下一篇：bzoj 2718: [Violet 4] （floyed+匈牙利算法）