Dowemo

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>


using namespace std;


const int maxn = 1005;


const int 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");


 else


 printf("%dn",ans);


 }


 return 0;


}


/*


2


5 5


.....


.J###


..#F#


..###


#####


3 3


FFF


FJF


FFF


*/









Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs