Dowemo
0 0 0 0

Topic links: https://vjudge. net/problem/UVA-11624.
a zone, j representative, f representative fire, # represents a wall, a, and each second can be spread around the perimeter, and a
Analysis: it's very easy to think of susan, but the problem of the problem pit is slightly more, the bug + look at the questions, the most easily thought

Pit point:
1, first initialization of the problem, all the start time should be infinity.
2, fire, the subject is fires.
3, queue empty

#include <bits/stdc++.h>usingnamespacestd;constint maxn = 1005;constint inf = 0x3f3f3f3f;struct node
{
 int x,y,step;
 node() {}
 node(int _x,int _y,int _step)
 {
 x = _x;
 y = _y;
 step = _step;
 }
};int n,m;char a[maxn][maxn];int vis[maxn][maxn];int step[maxn][maxn];int dx[] = {0,-1,1,0};int dy[] = {1,0,0,-1};queue<node>q;void init()
{
 while(!q.empty())
 q.pop();
 memset(vis,0,sizeof(vis));
 memset(step,inf,sizeof(step));
}void bfsf()
{
 while(!q.empty())
 {
 node now = q.front();
 q.pop();
 for(int i=0;i<4;i++)
 {
 int tx = now.x+dx[i];
 int ty = now.y+dy[i];
 if(tx<0 || tx>=n || ty<0 || ty>=m)
 continue;
 if(vis[tx][ty] || a[tx][ty]=='#')
 continue;
 vis[tx][ty] = 1;
 step[tx][ty] = now.step+1;
 q.push(node(tx,ty,now.step+1));
 }
 }
}int bfs(int x,int y)
{
 memset(vis,0,sizeof(vis));
 q.push(node(x,y,0));
 vis[x][y] = 1;
 while(!q.empty())
 {
 node now = q.front();
 q.pop();
 if(now.x==0 || now.y==0 || now.x==n-1 || now.y==m-1)
 return now.step+1;
 for(int i=0;i<4;i++)
 {
 int tx = now.x+dx[i];
 int ty = now.y+dy[i];
 if(tx<0 || tx>=n || ty<0 || ty>=m)
 continue;
 if(vis[tx][ty] || a[tx][ty]=='#')
 continue;
 if(now.step+1<step[tx][ty])
 {
 vis[tx][ty] = 1;
 q.push(node(tx,ty,now.step+1));
 }
 }
 }
 return -1;
}int main(void)
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
 init();
 scanf("%d %d",&n,&m);
 int x1,y1;
 for(int i=0;i<n;i++)
 {
 scanf("%s",a[i]);
 for(int j=0;j<m;j++)
 {
 if(a[i][j]=='J')
 x1 = i,y1 = j;
 if(a[i][j]=='F')
 {
 q.push(node(i,j,0));
 vis[i][j] = 1;
 step[i][j] = 0;
 }
 }
 }
 bfsf();
 int ans = bfs(x1,y1);
 if(ans==-1)
 puts("IMPOSSIBLE");
 elseprintf("%dn",ans);
 }
 return0;
}/*
2
5 5
.....
.J###
..#F#
..###
#####
3 3
FFF
FJF
FFF
*/



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs