傳送門：

http://acm.hdu.edu.cn/showproblem.php?pid=1180

詭異的樓梯

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 18382????Accepted Submission(s): 4864

Problem Description Hogwarts正式開學(xué)以后,Harry發(fā)現(xiàn)在Hogwarts里,某些樓梯并不是靜止不動的，相反,他們每隔一分鐘就變動一次方向.
比如下面的例子里,一開始樓梯在豎直方向,一分鐘以后它移動到了水平方向,再過一分鐘它又回到了豎直方向.Harry發(fā)現(xiàn)對他來說很難找到能使得他最快到達(dá)目的地的路線,這時Ron(Harry最好的朋友)告訴Harry正好有一個魔法道具可以幫助他尋找這樣的路線,而那個魔法道具上的咒語,正是由你纂寫的.

?

Input 測試數(shù)據(jù)有多組，每組的表述如下：
第一行有兩個數(shù),M和N,接下來是一個M行N列的地圖,'*'表示障礙物,'.'表示走廊,'|'或者'-'表示一個樓梯,并且標(biāo)明了它在一開始時所處的位置:'|'表示的樓梯在最開始是豎直方向,'-'表示的樓梯在一開始是水平方向.地圖中還有一個'S'是起點(diǎn),'T'是目標(biāo),0<=M,N<=20,地圖中不會出現(xiàn)兩個相連的梯子.Harry每秒只能停留在'.'或'S'和'T'所標(biāo)記的格子內(nèi).

?

Output 只有一行,包含一個數(shù)T,表示到達(dá)目標(biāo)的最短時間.
注意:Harry只能每次走到相鄰的格子而不能斜走,每移動一次恰好為一分鐘,并且Harry登上樓梯并經(jīng)過樓梯到達(dá)對面的整個過程只需要一分鐘,Harry從來不在樓梯上停留.并且每次樓梯都恰好在Harry移動完畢以后才改變方向.

?

Sample Input 5 5 **..T **.*. ..|.. .*.*. S....

?

Sample Output 7 Hint Hint 地圖如下：

?

Source Gardon-DYGG Contest 1

?

Recommend JGShining???|???We have carefully selected several similar problems for you:??1175?1072?1240?1253?1242? 分析： 超級經(jīng)典的搜索問題之一 需要注意的地方： 1.要搜的點(diǎn)有沒有越界 2.要搜的點(diǎn)是否搜過 3.要搜的點(diǎn)是不是障礙物 4.如果要搜的點(diǎn)是樓梯，判斷樓梯此時的狀態(tài)，是能直接通過樓梯，還是需要等樓梯翻轉(zhuǎn)過來 5.樓梯對面的點(diǎn)如果搜過了，或者越界了，或者是障礙物，那么就沒有走樓梯的必要 本題的重點(diǎn)在于樓梯狀態(tài)的判斷，因為樓梯狀態(tài)是隨時間變化的 code： #include<bits/stdc++.h> using namespace std; #define max_v 25 struct node {int x,y,t; }; char G[max_v][max_v]; int vis[max_v][max_v]; int dir[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; int n,m,sx,sy,fx,fy,tme; bool isout(int x,int y)//判斷能否繼續(xù)搜 {if(x<0||x>=n||y<0||y>=m)//越界return 1;if(vis[x][y]==1)//搜過return 1;if(G[x][y]=='*')//障礙物return 1;return 0; } bool isgo(node t,char x,int d)//判斷是不是需要等待樓梯轉(zhuǎn)動 {t.t+=1;if(x=='|'){if(d%2==0&&t.t%2==0)return 1;if(d%2==1&&t.t%2==1)return 1;return 0;}else if(x=='-'){if(d%2==1&&t.t%2==0)return 1;if(d%2==0&&t.t%2==1)return 1;return 0;} } void bfs() {memset(vis,0,sizeof(vis));//是否走過標(biāo)記位重置queue<node> q;node p,next;p.x=sx;//起點(diǎn)初始化p.y=sy;p.t=0;vis[p.x][p.y]=1;q.push(p);//隊列初始化while(!q.empty()){p=q.front();q.pop();if(p.x==fx&&p.y==fy)//判斷是否到達(dá)終點(diǎn) {tme=p.t;return ;}//四個方向搜for(int i=0; i<4; i++){next.x=p.x+dir[i][0];next.y=p.y+dir[i][1];//判斷越界if(isout(next.x,next.y))continue;if(G[next.x][next.y]=='.')//可行點(diǎn)之一 . {next.t=p.t+1;vis[next.x][next.y]=1;q.push(next);}else //如果是樓梯 {if(isout(next.x+dir[i][0],next.y+dir[i][1]))//判斷樓梯對面點(diǎn)能不能走continue;if(isgo(p,G[next.x][next.y],i))//樓梯不需要等，直接走 {next.x+=dir[i][0];next.y+=dir[i][1];next.t=p.t+1;vis[next.x][next.y]=1;q.push(next);}else //需要等樓梯翻轉(zhuǎn)過來才能走 {next.x=p.x;next.y=p.y;next.t=p.t+1;q.push(next);}}}} } int main() {while(cin>>n>>m){for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>G[i][j];if(G[i][j]=='S')//找起點(diǎn) {G[i][j]='.';sx=i;sy=j;}if(G[i][j]=='T')//找終點(diǎn) {G[i][j]='.';fx=i;fy=j;}}}bfs();cout<<tme<<endl;}return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的HDU 1180 诡异的楼梯（超级经典的bfs之一，需多回顾)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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