UVA 11624 Fire!

在一个迷宫里,'#'代表不能走的的墙,'.'代表可以走的广场,'J'代表人,'F'代表火,火每分钟能把其周围上下左右的四个地方给烧掉,凡是给烧掉的地方人就不能再走了,只要人能走到

迷宫的边界上就能传送出去,问人的逃出去的最小时间

因为传送出去还要一分钟,所以答案应该是人到达边界的时间在加上1,因为刚开始没有考虑着火的'F'有多个地方,所以wa了好久,先bfs火的情况,将火能到的每个点的最小时间记录

下来,然后bfs人的路径,如果人到达该点的时间小于之前记录的火到达该点的时间,则能走

至于着火的地方可能有多个,将多个点记录到队列里面同时bfs

  1 #include<cstdio>
  2 #include<queue>
  3 #include<cstring>
  4 using namespace std;
  5 #define M 1111
  6 #define inf 0x3f3f3f
  7 int vis[M][M],n,m,dis[M][M];
  8 char mp[M][M];
  9 struct point{
 10     int x,y;
 11     int time;
 12     point (int xx,int yy,int tt)
 13     {
 14         x=xx;
 15         y=yy;
 16         time=tt;
 17     }
 18 };
 19 struct node{
 20     int x,y;
 21     int time;
 22 };
 23 int dx[5]={-1,0,0,1};
 24 int dy[5]={0,-1,1,0};
 25 int x1,x2[M],y1,y2[M];
 26 queue<point>Q;
 27 void bfs1()
 28 {
 29    // printf("%d %d
",dis[0][0],dis[0][1]);
 30     while (!Q.empty())
 31     {
 32         point now=Q.front();
 33         Q.pop();
 34         point next=now;
 35         for (int i=0;i<4;i++)
 36         {
 37             next.x=now.x+dx[i];
 38             next.y=now.y+dy[i];
 39             if (next.x<0||next.x>=n) continue;
 40             if (next.y<0||next.y>=m) continue;
 41             if (vis[next.x][next.y]) continue;
 42             if (mp[next.x][next.y]=='#') continue;
 43             vis[next.x][next.y]=1;
 44             next.time=now.time+1;
 45             if (dis[next.x][next.y]>next.time)
 46             dis[next.x][next.y]=next.time;
 47             Q.push(next);
 48         }
 49     }
 50     return ;
 51 }
 52 int bfs2()
 53 {
 54     queue<node>Q;
 55     memset(vis,0,sizeof(vis));
 56     node now,next;
 57     now.x=x1,now.y=y1;
 58     vis[x1][y1]=1;
 59     now.time=0;
 60     Q.push(now);
 61     while (!Q.empty())
 62     {
 63         now=Q.front();
 64         Q.pop();
 65         if (now.x==0||now.x==n-1||now.y==0||now.y==m-1)
 66             return now.time;
 67         for (int i=0;i<4;i++)
 68         {
 69             next.x=now.x+dx[i];
 70             next.y=now.y+dy[i];
 71             if (next.x<0||next.x>=n) continue;
 72             if (next.y<0||next.y>=m) continue;
 73             if (vis[next.x][next.y]) continue;
 74             if (mp[next.x][next.y]=='#') continue;
 75             next.time=now.time+1;
 76             if (next.time>=dis[next.x][next.y]) continue;
 77             vis[next.x][next.y]=1;
 78             Q.push(next);
 79         }
 80     }
 81     return -1;
 82 }
 83 int main()
 84 {
 85     int i,j,t;
 86     scanf("%d",&t);
 87     while (t--){
 88     scanf("%d %d",&n,&m);
 89     int flag1=0;
 90     while (!Q.empty()) Q.pop();
 91     memset(dis,inf,sizeof(dis));
 92     memset(vis,0,sizeof(vis));
 93     for (i=0;i<n;i++){
 94         for (j=0;j<m;j++){
 95             scanf(" %c",&mp[i][j]);
 96             if (mp[i][j]=='J') x1=i,y1=j,flag1=1;
 97             if (mp[i][j]=='F') {
 98                 point tem(i,j,0);
 99                 dis[i][j]=0;
100                 vis[i][j]=1;
101                 Q.push(tem);
102             }
103         }
104     }
105     if (!flag1){
106         printf("IMPOSSIBLE
");
107         continue;
108     }
109     bfs1();
110     int x=bfs2();
111     if (x!=-1) printf("%d
",x+1);
112     else printf("IMPOSSIBLE
");
113     }
114     return 0;
115 }