UVA 10047 The Monocycle（BFS）

思路：BFS即可。

#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<algorithm>#define debuusing namespace std;const int maxn=30;const int dx[]= {-1,0,1,0};const int dy[]= {0,1,0,-1};struct Node{    int x,y,dir,col,t;    Node(int x=0,int y=0,int dir=0,int col=0,int t=0):x(x),y(y),dir(dir),col(col),t(t) {}};queue<Node> q;char st[maxn][maxn];int n,m,stx,sty,edx,edy;int vis[maxn][maxn][5][6];int isIn(int x,int y){    return x>=0&&x<n&&y>=0&&y<m;}int isGet(Node tmp){    return tmp.x==edx&&tmp.y==edy&&tmp.col==0;}void solve(int x,int y,int dir,int col,int t){    int ans,flag=0;    memset(vis,0,sizeof(vis));    while(!q.empty()) q.pop();    q.push(Node(x,y,dir,col,t)),vis[x][y][dir][col]=1;    while(!q.empty())    {        Node now=q.front();        q.pop();        if(isGet(now))        {            flag=1;            ans=now.t;            break;        }        {            Node nt;            nt.x=now.x+dx[now.dir];            nt.y=now.y+dy[now.dir];            nt.dir=now.dir,nt.col=(now.col+1)%5,nt.t=now.t+1;            if(isIn(nt.x,nt.y)&&(!vis[nt.x][nt.y][nt.dir][nt.col])&&st[nt.x][nt.y]!='#')            {                vis[nt.x][nt.y][nt.dir][nt.col]=1;                q.push(nt);            }        }        {            Node nt;            nt.x=now.x,nt.y=now.y,nt.t=now.t+1;            nt.dir=(now.dir+3)%4,nt.col=now.col;            if(!vis[nt.x][nt.y][nt.dir][nt.col])            {                vis[nt.x][nt.y][nt.dir][nt.col]=1;                q.push(nt);            }            nt.dir=(now.dir+1)%4;            if(!vis[nt.x][nt.y][nt.dir][nt.col])            {                vis[nt.x][nt.y][nt.dir][nt.col]=1;                q.push(nt);            }        }    }    if(flag) printf("minimum time = %d sec/n",ans);    else printf("destination not reachable/n");}int main(){#ifdef debug    freopen("in.in","r",stdin);#endif // debug    int t,cas=0;    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))    {        cas++;        if(cas!=1) printf("/n");        printf("Case #%d/n",cas);        for(int i=0; i<n; i++)        {            getchar();            scanf("%s",st[i]);            for(int j=0; j<m; j++)            {                if(st[i][j]=='S') stx=i,sty=j;                else if(st[i][j]=='T') edx=i,edy=j;            }        }        solve(stx,sty,0,0,0);    }    return 0;}