题目大意：
这是一个放火逃生的游戏，就是给出来一个迷宫，迷宫里面有人‘J’和火焰‘F’当然这些火焰可能不止一处，然后问这个人最快从迷宫里面逃出来需要多久
////////////////////////////////////////////////////////////
最简单明了的办法就是写两个BFS，这样很容易理解，好吧，那就这么办吧,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
试一下吧。
第一次提交wa，只想到了火焰可能有多处，实际上还有可能没有火焰......
#include
#include
#include<string.h>
using namespace std;
#define maxn 1005
const int oo = 0xfffffff;
struct node{int x, y;};
node JoeSite, FireSite[maxn*maxn];//因为火可能不止一处，所以开一个数组保存所有的火焰的位置
char G[maxn][maxn];
int vJoe[maxn][maxn], vFire[maxn][maxn];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int M, N, nFire;
void BfsFire()
{
node s, q;
queue Q;
int i;
for(i=0; i {
Q.push(FireSite[i]);
vFire[ FireSite[i].x ][ FireSite[i].y ] = 1;
}
while(Q.size())
{
s = Q.front();Q.pop();
for(i=0; i<4; i++)
{
q = s;
q.x += dir[i][0];
q.y += dir[i][1];
if(q.x>=0&&q.x=0&&q.y‘#‘ && vFire[q.x][q.y]==oo)
{
vFire[q.x][q.y] = vFire[s.x][s.y] + 1;
Q.push(q);
}
}
}
}
int IsBorder(int x, int y)//判断是否是边界并且是否比火焰先到达
{
if( (x==0 || x==M-1 || y==0 || y==N-1) && vJoe[x][y] < vFire[x][y] )
return 1;
return 0;
}
int BfsJoe()
{
queue Q;
node s, q;
int i;
vJoe[JoeSite.x][JoeSite.y] = 1;
Q.push(JoeSite);
while(Q.size())
{
s = Q.front();Q.pop();
if(IsBorder(s.x, s.y) == 1)
return vJoe[s.x][s.y];
for(i=0; i<4; i++)
{
q = s;
q.x += dir[i][0];
q.y += dir[i][1];
if(q.x>=0&&q.x=0&&q.y‘#‘ && vJoe[q.x][q.y]==0)
{
vJoe[q.x][q.y] = vJoe[s.x][s.y] + 1;
Q.push(q);
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int i, j, ans;
scanf("%d%d", &M, &N);
nFire = 0;
for(i=0; i {
scanf("%s", G[i]);
for(j=0; j {
vJoe[i][j] = 0;
vFire[i][j] = oo;
if(G[i][j] == ‘J‘)
JoeSite.x = i, JoeSite.y = j;
if(G[i][j] == ‘F‘)
{
FireSite[nFire].x = i;
FireSite[nFire++].y = j;
}
}
}
BfsFire();
ans = BfsJoe();
if(ans == -1)
printf("IMPOSSIBLE\n");
else
printf("%d\n", ans);
}
return 0;
}
J - Fire!
京公网安备 11010802041100号