题目大意：有一个迷宫，Joe在迷宫中，Joe只需要走到迷宫边就可以走出迷宫，但是迷宫中有障碍和火，障碍会让Joe
无法通过，而火会燃烧，Joe每走一步火会向四周燃烧，Joe不能到达火的区域
思路：bfs 有多个起点，火的起点优先，且记录这个点是火先到达还是Joe，Joe需要在火之前走出迷宫，并且不能走到
火燃烧的地方，bfs的时候把火放到人之前就可以了。主要是在bfs的时候注意火和Joe要同时bfs不然会超时
#include<stdio.h> #include<string.h> int n,m; struct node{ int x; int y; int step; int f; //判断这个点是不是火先走过的 }q[1000005]; char map[1005][1005];//存迷宫 int book[1005][1005];//标记数组 int x1,y3; int check(int a,int b){//判断可不可以走 if(a>=0&&a<n&&b>=0&&b<m&&map[a][b]!='#'&&book[a][b]==0) return 1; return 0; } int bfs(); int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//四个方向 int main(void) { int num; scanf("%d",&num); while(num--){ scanf("%d%d",&n,&m); getchar(); int i,j; for(i=0;i<n;i++){ gets(map[i]); int j; for(j=0;j<m;j++){ if(map[i][j]=='J'){ x1=i; y3=j; } } } int ans=bfs(); if(ans!=-1){ printf("%d\n",ans); } else printf("IMPOSSIBLE\n"); } return 0; } int bfs(){ memset(book,0,sizeof(book)); int head=0; int tail=0; int i,j; for(i=0;i<n;i++){//把所有的fire和joe加到队列中 for(j=0;j<m;j++){ if(map[i][j]=='F'){ q[tail].x=i; q[tail].y=j; q[tail].step=0; q[tail].f=1; tail++; book[i][j]=1; } } } q[tail].x=x1; q[tail].y=y3; q[tail].step=0; q[tail].f=0; book[x1][y3]=1; tail++; while(head<tail){ if((q[head].x==n-1||q[head].y==m-1||q[head].x==0||q[head].y==0)&&q[head].f==0) return q[head].step+1;//判断这个点是不是走出去了，而且是Joe int i; for(i=0;i<4;i++){ int tx=q[head].x+dir[i][0]; int ty=q[head].y+dir[i][1]; if(check(tx,ty)){ q[tail].x=tx; q[tail].y=ty; q[tail].step=q[head].step+1; q[tail].f=q[head].f; book[tx][ty]=1; tail++; } } head++; } return -1; }
