uvaoj 11624 - Fire!
标题:一人で迷宮から外へ逃げると、迷宮の中に火があり、毎秒周囲に一コマ伸びる.障害物も火も届かない.逃げ出す最短時間は?
考え方:BFS
コードは次のとおりです.
考え方:BFS
コードは次のとおりです.
#include
#include
#include
#include
#include
using namespace std;
struct pos
{
int x,y;
pos(int x=0,int y=0):x(x),y(y){}
};
int r,c;
bool legel(pos t)
{
if(t.x<0)return 0;
if(t.y<0)return 0;
if(t.x>=r)return 0;
if(t.y>=c)return 0;
return 1;
}
int dir[4][2]={-1,0,0,-1,1,0,0,1};
vector sav;
char maze[1005][1005];
int ftime[1005][1005];//
int rtime[1005][1005];//
void bfs(int x,int y)//
{
queue s;
s.push(pos(x,y));
while(!s.empty())
{
pos now=s.front();
s.pop();
for(int d=0;d<4;++d)
{
pos tmp=pos(now.x+dir[d][0],now.y+dir[d][1]);
if(!legel(tmp))continue;
if(maze[tmp.x][tmp.y]=='#')continue;
if(ftime[tmp.x][tmp.y]>(ftime[now.x][now.y]+1)||ftime[tmp.x][tmp.y]==-1)
{
ftime[tmp.x][tmp.y]=ftime[now.x][now.y]+1;
s.push(tmp);
}
}
}
}
void solve(int sx,int sy)
{
queue q;
q.push(pos(sx,sy));
rtime[sx][sy]=0;
while(!q.empty())
{
pos now=q.front();
q.pop();
for(int d=0;d<4;++d)
{
pos tmp=pos(now.x+dir[d][0],now.y+dir[d][1]);
if(!legel(tmp))continue;
if(maze[tmp.x][tmp.y]=='#')continue;
int tt=rtime[now.x][now.y]+1;
if(ftime[tmp.x][tmp.y]<=tt&&ftime[tmp.x][tmp.y]!=-1)continue;
if(rtime[tmp.x][tmp.y]>tt||rtime[tmp.x][tmp.y]==-1)
{
rtime[tmp.x][tmp.y]=tt;
q.push(tmp);
}
}
}
int ans=1000000;
for(int i=0;i