UVA

**********************************************************

分析：这是一个放火逃生的游戏，就是给出来一个迷宫，迷宫里面有人‘J’和火焰‘F’当然这些火焰可能不止一处，然后问这个人最快从迷宫里面逃出来需要多久，最简单明了的办法就是写两个BFS

*: 火焰可能有多处，还有可能没有火焰

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <algorithm>
  5 #include <stdlib.h>
  6 #include<queue>
  7 #include<math.h>
  8 using namespace std;
  9 
 10 #define N 1250
 11 #define maxn 115200
 12 #define INF 0x3f3f3f3f
 13 
 14 char s[N][N];
 15 int vj[N][N],vf[N][N];
 16 int n,m,k;
 17 
 18 int dir[4][2]={ {0,1},{0,-1},{1,0},{-1,0} };
 19 
 20 struct node
 21 {
 22     int x,y;
 23 }F[N*N];
 24 node J;
 25 
 26 void Bfsf()
 27 {
 28     node start,q;
 29     queue<node>Q;
 30 
 31     for(int i=0;i<k;i++)
 32     {
 33         Q.push(F[i]);
 34         vf[F[i].x][F[i].y]=1;
 35     }
 36 
 37     while(Q.size())
 38     {
 39         start=Q.front();
 40         Q.pop();
 41 
 42         for(int i=0;i<4;i++)
 43         {
 44             q=start;
 45             q.x+=dir[i][0];
 46             q.y+=dir[i][1];
 47 
 48             if(q.x>0&&q.x<=m&&q.y>=0&&q.y<n&&s[q.x][q.y]!= '#'&&vf[q.x][q.y]==INF)
 49             {
 50                 vf[q.x][q.y]=vf[start.x][start.y]+1;///在上次的火标记的数基础上再加1
 51                 Q.push(q);
 52             }
 53         }
 54     }
 55 }
 56 
 57 int Bfsj()
 58 {
 59     queue<node>Q;
 60     node start,q;
 61 
 62     vj[J.x][J.y]=1;
 63     Q.push(J);
 64 
 65     while(Q.size())
 66     {
 67         start=Q.front();
 68         Q.pop();
 69 
 70         if((start.x==1||start.x==m||start.y==0||start.y==n-1)&&vj[start.x][start.y]<vf[start.x][start.y])
 71             return vj[start.x][start.y];///人获得的标记数比火标记的数小，意味着人先到达，则可以逃生
 72 
 73         for(int i=0;i<4;i++)
 74         {
 75             q=start;
 76             q.x+=dir[i][0];
 77             q.y+=dir[i][1];
 78 
 79             if(q.x>0&&q.x<=m&&q.y>=0&&q.y<n&&vj[q.x][q.y]==0&&s[q.x][q.y] != '#')
 80             {
 81                 vj[q.x][q.y]=vj[start.x][start.y]+1;
 82                 Q.push(q);
 83             }
 84         }
 85     }
 86     return -1;
 87 }
 88 
 89 int main()
 90 {
 91     int T,i,j;
 92 
 93     scanf("%d", &T);
 94 
 95     while(T--)
 96     {
 97         scanf("%d%d",&m,&n);
 98         k=0;///火的个数
 99 
100         for(i=1;i<=m;i++)
101         {
102             scanf("%s", s[i]);
103             for(j=0;j<n;j++)
104             {
105                 vj[i][j]=0;
106                 vf[i][j]=INF;
107 
108                 if(s[i][j]=='J')
109                     J.x=i,J.y=j;
110                 if(s[i][j]=='F')
111                 {
112                     F[k].x=i;
113                     F[k++].y=j;
114                 }
115             }
116         }
117 
118         Bfsf();
119         int ans=Bfsj();
120 
121         if(ans==-1)
122             printf("IMPOSSIBLE
");
123         else
124             printf("%d
",ans);
125     }
126     return 0;
127 }