# uva 11624 Fire!(bfs预加工)

www.MyException.Cn  网友分享于：2014-04-18  浏览：2次
uva 11624 Fire!(bfs预处理)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=116#problem/A

```#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#define LL long long
#define _LL __int64

using namespace std;
const int maxn = 1010;
const int INF = 0x3f3f3f3f;
struct node
{
int x,y;
int step;
};
queue <node> que;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int jx,jy;
char map[maxn][maxn],s[maxn];
int time[maxn][maxn],vis[maxn][maxn];
int n,m;
int ans;

//预处理每个格子（不是障碍格）着火的时刻
void solve()
{
memset(vis,0,sizeof(vis));
memset(time,INF,sizeof(time));
while(!que.empty()) que.pop();

for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
if(map[i][j] == 'F')
{
que.push((struct node){i,j,1});
time[i][j] = 1;
vis[i][j] = 1;
}
}

while(!que.empty())
{
struct node u = que.front();
que.pop();

for(int d = 0; d < 4; d++)
{
int x = u.x + dir[d][0];
int y = u.y + dir[d][1];
if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#' && !vis[x][y])
{
vis[x][y] = 1;
que.push((struct node){x,y,u.step+1});
time[x][y] = u.step+1;
}
}
}
}

//寻找joe出口的最短路径
bool bfs()
{
memset(vis,0,sizeof(vis));
while(!que.empty()) que.pop();

vis[jx][jy] = 1;
que.push((struct node){jx,jy,1});

while(!que.empty())
{
struct node u = que.front();
que.pop();

if(u.x == 1 || u.x == n || u.y == 1 || u.y == m)
{
ans = u.step;
return true;
}

for(int d = 0; d < 4; d++)
{
int x = u.x + dir[d][0];
int y = u.y + dir[d][1];
if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#' && !vis[x][y])
{
if(u.step + 1 < time[x][y]) //只有当该格子没着火才进队列
{
time[x][y] = 1;
que.push((struct node){x,y,u.step+1});
}
}
}
}
return false;
}

int main()
{
int test;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
{
scanf("%s",map[i]+1);
for(int j = 1; j <= m; j++)
if(map[i][j] == 'J')
{
jx = i;
jy = j;
}
}

solve();
if(bfs())
printf("%d\n",ans);
else printf("IMPOSSIBLE\n");

}
return 0;
}
```