UOJ Logo BY_wenghaozhe的博客

博客

2017-12-31 15:05:02 By BY_wenghaozhe

include iostream

include cstring

include cstdio

include queue

define M 500

using namespace std; struct node{ int x,y; int step; }; int mv[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int m,n; char mark[M][M]; int mp[M][M]; int sx,sy,ex,ey; queueque; bool ok(node t) { if(t.x>=1&&t.x<=n && t.y>=1 &&t.y<=m); return true; return false; } int bfs() { memset(mp,0,sizeof(mp)); node head; head.x = sx; head.y = sy; head.step=0; mp[sx][sy]=1; que.push(head); while( !que.empty() )
{ node t,s; t = que.front(); que.pop(); if(t.x==ex&&t.y==ey) return t.step; for(int i=0; i<4; i++) { s.x = t.x+mv[i][0]; s.y = t.y+mv[i][1]; s.step = t.step+1; if(ok(s)&&!mp[s.x][s.y] &&mark[s.x][s.y]!='#') { mp[s.x][s.y] = 1; que.push(s); } } } } int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) for(int j=1; j<=n; j++) cin>>mark[i][j]; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ if(mark[i][j]=='S')sx=i,sy=j; if(mark[i][j]=='T')ex=i,ey=j; } //cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<endl;
cout<<bfs(); }

/*c++一本通 走出迷宫 1254 谢谢

*/

评论

BY_wenghaozhe
对的
xukuan
# 这Markdown我给满分
xukuan
@

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。