题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1180
题目大意：迷宫中有一堆楼梯，楼梯横竖变化。这些楼梯在奇数时间会变成相反状态，通过楼梯会顺便到达前进方向的下一个点（跳过楼梯）。
同时可以在原地等待，问到达终点的最少时间。
解题思路：
很有趣的一个题。
还是先BFS，对于一个楼梯，change函数负责计算出走楼梯能够到达的新的X和Y，再判一次是否越界或不可达。
注意，在'.'点是可以原地等待的，需要额外Push这个点，这也是这题不会出现走不出迷宫的数据的原因，否则因为出不去迷宫，会不停在一个点BFS。
然后，程序就爆了。
#include "cstdio"
#include "string"
#include "cstring"
#include "iostream"
#include "queue"
using namespace std;
char map[][];
int n,m,sx,sy,ex,ey,dir[][]={-,,,,,-,,},vis[][];
struct status
{
int x,y,dep;
status(int x,int y,int dep):x(x),y(y),dep(dep) {}
};
status change(status s,int dir,char c,int dep)
{
if(dep%) c=(c=='|'?'-':'|');
if(c=='|')
{
if(dir==) return status(s.x-,s.y,);
if(dir==) return status(s.x+,s.y,);
if(dir==||dir==) return status(-,-,);
}
if(c=='-')
{
if(dir==||dir==) return status(-,-,);
if(dir==) return status(s.x,s.y-,);
if(dir==) return status(s.x,s.y+,);
}
}
int bfs(int x,int y)
{
queue<status> Q;
Q.push(status(x,y,));
vis[x][y]=true;
while(!Q.empty())
{
status t=Q.front();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][];
if(X<||X>n||Y<||Y>m||vis[X][Y]||map[X][Y]=='*') continue;
if(map[X][Y]=='|'||map[X][Y]=='-')
{
status nw=change(status(X,Y,),s,map[X][Y],t.dep);
X=nw.x;Y=nw.y;
}
if(X<||X>n||Y<||Y>m||vis[X][Y]||map[X][Y]=='*') continue;
vis[X][Y]=true;
if(X==ex&&Y==ey) return t.dep+;
Q.push(status(X,Y,t.dep+));
}
if(map[t.x][t.y]!='|'||map[t.x][t.y]!='-') Q.push(status(t.x,t.y,t.dep+));
}
return -;
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
string tt;
while(cin>>n>>m)
{
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
cin>>tt;
for(int j=;j<tt.size();j++)
{
map[i][j+]=tt[j];
if(tt[j]=='S') {sx=i;sy=j+;}
if(tt[j]=='T') {ex=i;ey=j+;}
}
}
int ans=bfs(sx,sy);
cout<<ans<<endl;
}
}
| 11891440 | 2014-10-17 01:13:57 | Accepted | 1180 | 15MS | 308K | 2067 B | C++ | Physcal |