hdu1242 Rescue DFS（路徑探索題）

這里我定義的路徑探索題指 找某路能夠到達(dá)目的地，每次走都有方向，由于是探索性的走 之后要后退 那些走過(guò)的狀態(tài)都還原掉

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1242

Rescue

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15884????Accepted Submission(s): 5759


Problem Description Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.?

Process to the end of the file.

Output For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."?

Sample Input 7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........
Sample Output 13

大意：天使 a被關(guān) ?朋友r(可以有多個(gè))要去救天使 r要繞過(guò)#（障礙物）和x（守衛(wèi)）去尋找天使a 不能穿過(guò)障礙物 要走守衛(wèi)那一步必須打敗守衛(wèi) 時(shí)間為2，其他每步時(shí)間為1；

問(wèn)找到天使的最短時(shí)間；

思路：用搜索做，由于r可以有多個(gè)，所以從天使a出發(fā)，每次都有四個(gè)方向可以走 用visit[x][y]記錄該點(diǎn)是否被走過(guò)，如往一個(gè)方向走但是另一個(gè)點(diǎn)被visit過(guò)就不會(huì)重復(fù)走了

往其中一個(gè)方向走后繼續(xù)進(jìn)行dfs直到找到r或者無(wú)路可走 注意由于是探索性的走，走完進(jìn)行DFS后記得往后退，狀態(tài)還原；

代碼如下：

#include<iostream> using namespace std; #include<string.h> #define max 205 char map[max][max]; long a[100000],step,sum,n,m,visited[max][max]; long directions[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//DFS 不用隊(duì)列，不用結(jié)構(gòu)體 /**7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........ output<<13*/ void DFS(int x,int y) {int i,mx,my;if(map[x][y]=='r')a[sum++]=step;else if(map[x][y]!='#'){for(i=0;i<4;i++){mx=x+directions[i][0];my=y+directions[i][1];if(map[mx][my]!='#'&&mx>=1&&mx<=n&&my>=1&&my<=m&&!visited[mx][my])//不是墻并且沒(méi)走過(guò){if(map[x][y]=='x')step++;step++;visited[mx][my]=1;DFS(mx,my); //所以關(guān)鍵要得到值的是遞歸的這一步 推導(dǎo)的時(shí)候讓這個(gè)的下一個(gè)DFS就是到達(dá)朋友那點(diǎn)比較好理解為什么后面要還原visited[mx][my]=0;//這一步的原因，上面DFS進(jìn)行完后要將狀態(tài)還原step--; //下面這些都要還原if(map[x][y]=='x')step--;}}} }int main() {long i,j,x,y,min;while(cin>>n>>m){memset(visited,0,sizeof(visited));sum=0;step=0;min=max;for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>map[i][j];if(map[i][j]=='a')//記錄天使的地址{x=i;y=j;}}}visited[x][y]=1;DFS(x,y);if(sum==0)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;else{for(i=0;i<sum;i++)if(a[i]<min)min=a[i];cout<<min<<endl;}}return 0; }

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

posted on 2014-07-29 21:23 france 閱讀(...) 評(píng)論(...) 編輯 收藏

轉(zhuǎn)載于:https://www.cnblogs.com/france/p/4808704.html

總結(jié)

以上是生活随笔為你收集整理的hdu1242 Rescue DFS（路径探索题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。