HDU 1180 詭異的樓梯 (DFS)
詭異的樓梯
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 6472 Accepted Submission(s): 1525
Problem Description
Hogwarts正式開學以後,Harry發現在Hogwarts裡,某些樓梯並不是靜止不動的，相反,他們每隔一分鐘就變動一次方向.
比如下面的例子裡,一開始樓梯在豎直方向,一分鐘以後它移動到了水平方向,再過一分鐘它又回到了豎直方向.Harry發現對他來說很難找到能使得他最快到達目的地的路線,這時Ron(Harry最好的朋友)告訴Harry正好有一個魔法道具可以幫助他尋找這樣的路線,而那個魔法道具上的咒語,正是由你纂寫的.
Input
測試數據有多組，每組的表述如下：
第一行有兩個數,M和N,接下來是一個M行N列的地圖,'*'表示障礙物,'.'表示走廊,'|'或者'-'表示一個樓梯,並且標明了它在一開始時所處的位置:'|'表示的樓梯在最開始是豎直方向,'-'表示的樓梯在一開始是水平方向.地圖中還有一個'S'是起點,'T'是目標,0<=M,N<=20,地圖中不會出現兩個相連的梯子.Harry每秒只能停留在'.'或'S'和'T'所標記的格子內.
Output
只有一行,包含一個數T,表示到達目標的最短時間.
注意:Harry只能每次走到相鄰的格子而不能斜走,每移動一次恰好為一分鐘,並且Harry登上樓梯並經過樓梯到達對面的整個過程只需要一分鐘,Harry從來不在樓梯上停留.並且每次樓梯都恰好在Harry移動完畢以後才改變方向.
Sample Input
5 5
**..T
**.*.
..|..
.*.*.
S....
Sample Output
7
HintHint
地圖如下：
注意樓梯用過了1遍之後還可以再用 因為用來橫著走之後還可以豎著走 所以不標記樓梯是否走過
#include
#includevc3RyZWFtPgojaW5jbHVkZTxzdHJpbmcuaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTxtYXRoLmg+CiNpbmNsdWRlPHF1ZXVlPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgZmxhZ1syNV1bMjVdLHN1bSx4MSx6MSxkaXJbNF1bMl09ezAsLTEsLTEsMCwwLDEsMSwwfTsKY2hhciBtYXBbMjVdWzI1XTsKdHlwZWRlZiBzdHJ1Y3Qgbm9kZQp7CiAgICBpbnQgeCx5LHN0ZXAsZjsKfW5vZGU7CnF1ZXVlPG5vZGU+YTsKdm9pZCBjbGVhcigpCnsKICAgIHdoaWxlKCFhLmVtcHR5KCkpCiAgICBhLnBvcCgpOwp9CmludCBiZnMoaW50IHgxLGludCB6MSkKewogICAgbm9kZSBub3csbmV4dDsKICAgIG5vdy54PXgxO25vdy55PXoxO25vdy5zdGVwPTA7bm93LmY9MDsKICAgIGEucHVzaChub3cpOwogICAgd2hpbGUoIWEuZW1wdHkoKSkKICAgIHsKICAgICAgICBub3c9YS5mcm9udCgpOwogICAgICAgIGEucG9wKCk7CiAgICAgICAgaWYobm93LmY9PTEpCiAgICAgICAgewogICAgICAgICAgICBub3cuZj0wOwogICAgICAgICAgICBhLnB1c2gobm93KTsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaT0wO2k8NDtpJiM0MzsmIzQzOykKICAgICAgICB7CiAgICAgICAgICAgIG5leHQueD1ub3cueCYjNDM7ZGlyW2ldWzBdOwogICAgICAgICAgICBuZXh0Lnk9bm93LnkmIzQzO2RpcltpXVsxXTsKICAgICAgICAgICAgbmV4dC5zdGVwPW5vdy5zdGVwJiM0MzsxOwogICAgICAgICAgICBuZXh0LmY9MDsKICAgICAgICAgICAgaW50IHh4PW5leHQueDsKICAgICAgICAgICAgaW50IHl5PW5leHQueTsKICAgICAgICAgICAgaWYobWFwW3h4XVt5eV09PQ=="*'||flag[xx][yy]==1)
continue;
if(map[xx][yy]=='T')
return next.step;
if(map[xx][yy]=='|')
{
if((now.step%2==0&&(i==1||i==3))||now.step%2==1&&(i==0||i==2))
{
next.x=next.x+dir[i][0];
next.y=next.y+dir[i][1];
if(map[next.x][next.y]=='*'||flag[xx][yy]==1)
continue;
if(map[next.x][next.y]=='T')
return next.step;
flag[next.x][next.y]=1;
a.push(next);
}
else
{
next.x=next.x+dir[i][0];
next.y=next.y+dir[i][1];
next.step=next.step+1;
next.f=1;
if(map[next.x][next.y]=='*'||flag[xx][yy]==1)
continue;
if(map[next.x][next.y]=='T')
return next.step;
flag[next.x][next.y]=1;
a.push(next);
}
continue;
}
if(map[xx][yy]=='-')
{
if((now.step%2==0&&(i==0||i==2))||now.step%2==1&&(i==1||i==3))
{
next.x=next.x+dir[i][0];
next.y=next.y+dir[i][1];
if(map[next.x][next.y]=='T')
return next.step;
if(map[next.x][next.y]=='*'||flag[xx][yy]==1)
continue;
flag[next.x][next.y]=1;
a.push(next);
}
else
{
next.x=next.x+dir[i][0];
next.y=next.y+dir[i][1];
if(map[next.x][next.y]=='*'||flag[xx][yy]==1)
continue;
next.step=next.step+1;
next.f=1;
if(map[next.x][next.y]=='T')
return next.step;
flag[next.x][next.y]=1;
a.push(next);
}
continue;
}
flag[xx][yy]=1;
a.push(next);
}
}
}
int main()
{
int n,m,i,j;
while(~scanf("%d%d",&n,&m))
{
sum=0;
memset(flag,0,sizeof(flag));
memset(map,'*',sizeof(map));
clear();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
x1=i;
z1=j;
}
}
flag[x1][z1]=1;
sum=bfs(x1,z1);
cout<
