BFS

https://vjudge.net/problem/UVA-11624
题意：一个平面迷宫中有一个人，迷宫中有些点起火了，火和人每个单位时间只能向相邻的格子移动，其中有一些空间被墙壁占据，问这个人在不背或烧到的情况下，离开迷宫的最快时间。
题解：先对起火点进行BFS，求出每个方格被烧到的时间。然后再对起点进行BFS，如果走到该方格的时间小于被火烧到的时间，则说明该方格可以走，否则，该方格不能走。

#include<cstdio>
#include<string.h>
#include<queue>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
const int maxn=1010;
char g[maxn][maxn];
int vis[maxn][maxn];
int grade[maxn][maxn];
int to[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int sx,sy,R,C;
queue<int> fx;
queue<int> fy;
struct Node
{
    int x,y,step;

};
void Fire()
{
    memset(vis,0,sizeof(vis));
    memset(grade,0,sizeof(grade));
    queue<Node> fire;
    int Fx,Fy;
    while(!fx.empty())
    {
        Fx=fx.front();
        Fy=fy.front();
        vis[Fx][Fy]=1;
        fx.pop();
        fy.pop();
        fire.push(Node{Fx,Fy,0});
    }
    while(!fire.empty())
        {
            Node curr=fire.front(),next;
            fire.pop();
            next.step=curr.step+1;
            for(int i=0;i<4;i++)
            {
                next.x=curr.x+to[i][0];
                next.y=curr.y+to[i][1];
                if(next.x>=0&&next.x<=R&&next.y>=0&&next.y<=C&&
                   (g[next.x][next.y]=='.'||g[next.x][next.y]=='J')&&vis[next.x][next.y]==0)
                {
                    vis[next.x][next.y]=1;
                    grade[next.x][next.y]=next.step;
                    fire.push(next);
                }
            }
        }
}
int BFS()
{
        Fire();
    memset(vis,0,sizeof(vis));
    queue<Node> q;
    q.push(Node{sx,sy,0});
    vis[sx][sy]=1;
    while(!q.empty())
    {
        Node curr=q.front(),next;
        q.pop();
        if(curr.x==1||curr.x==R||curr.y==1||curr.y==C)
        {
            return curr.step+1;
        }
        next=curr;
        next.step=curr.step+1;
        for(int i=0;i<4;i++)
        {
            next.x=curr.x+to[i][0];
            next.y=curr.y+to[i][1];
            if(next.x>0&&next.x<=R&&next.y>0&&next.y<=C&&g[next.x][next.y]=='.'
               &&vis[next.x][next.y]==0&&(next.step<grade[next.x][next.y]||grade[next.x][next.y]==0))
            {
                vis[next.x][next.y]=1;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&R,&C);
        for(int i=1;i<=R;i++)
        {
            for(int j=1;j<=C;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='J') {sx=i;sy=j;}
                else if(g[i][j]=='F')
                {
                    fx.push(i);
                    fy.push(j);
                }
            }
        }
        int minute=BFS();
        if(minute!=-1) printf("%d\n",minute);
        else printf("IMPOSSIBLE\n");
    }
}

题意：
有一个独轮车，轮上有5个不同的颜色区域， 每个区域大小相等。 独轮车从一块瓷砖走向相邻的一块，轮子正好转1/5。只能走向相邻的上、下、左、右的瓷砖。车子左转90°，右转90°,以及前进都耗费1秒钟。开始时，蓝色轮子贴着地面，到达终点时，也是蓝色贴着地面。
如果可以到达的话，输出所需要的最短时间。
题解：设置四个不同的状态（坐标x，坐标y，当前方向,轮子颜色），分三个方向走。

#include<cstdio>
#include<string.h>
#include<queue>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
const int maxn=28;//0,1,2,3 北南西东
char g[maxn][maxn];
int vis[maxn][maxn][4][5];// x, y, 方向，轮子颜色
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//0,1,2,3 北南西东
int sx,sy,R,C,ex,ey;
struct Node
{
    int x,y,col,dir,step;

};
int leftRorate(int u)
{
    switch(u)
    {
        case 0:return 2;
        case 1:return 3;
        case 2:return 1;
        default:return 0;
    }
}
int rightRorate(int u)
{
    switch(u)
    {
        case 0:return 3;
        case 1:return 2;
        case 2:return 0;
        default:return 1;
    }
}
int BFS()
{
    //int vis[maxn][maxn][4][5];
    memset(vis,0,sizeof(vis));
    queue<Node> q;
    q.push(Node{sx,sy,0,0,0});
    vis[sx][sy][0][0]=1;
    while(!q.empty())
    {
        Node curr=q.front(),next;
        q.pop();
        if(curr.x==ex&&curr.y==ey&&curr.col==0)
        {
            return curr.step;
        }
        next=curr;
        next.step=curr.step+1;
        for(int i=0;i<3;i++)
        {
            if(i==0) {
                next.x=curr.x+to[curr.dir][0];
                next.y=curr.y+to[curr.dir][1];
                next.col=(curr.col+1)%5;
                next.dir=curr.dir;
            }
            else if(i==1)
            {
                next.x=curr.x;
                next.y=curr.y;
                next.col=curr.col;
                next.dir=leftRorate(curr.dir);
            }
            else
            {
                next.x=curr.x;
                next.y=curr.y;
                next.col=curr.col;
                next.dir=rightRorate(curr.dir);
            }
            if(next.x>=1&&next.x<=R&&next.y>=1&&next.y<=C&&
               vis[next.x][next.y][next.dir][next.col]==0&&g[next.x][next.y]!='#')
            {
                vis[next.x][next.y][next.dir][next.col]=1;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    int cas=1;
    while(scanf("%d%d",&R,&C)!=EOF,R+C)
    {
        if(cas!=1) printf("\n");
        for(int i=1;i<=R;i++)
        {
            for(int j=1;j<=C;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='S') {sx=i;sy=j;}
                else if(g[i][j]=='T'){ex=i;ey=j;}
            }
        }
        printf("Case #%d\n",cas++);
        int minute=BFS();
        if(minute!=-1)  printf("minimum time = %d sec\n",minute);
        else printf("destination not reachable\n");
    }
}