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");
}
}
