题目链接：https://cn.vjudge.net/problem/28833/origin

 

题目大意：

给1个n*m的网格，上面有的点能走，有的点不能走（墙），然后有的点是火源，火源和人一样，每次都是上下左右四个方向蔓延，速度一样是1，火也不可以从墙上跨过去，给你人的起点，终点是只要走到边界就行，就是走出矩阵，问你最小逃生时间。

 

思路：

先处理火源，把每个点最早到达的火源的时间记录下来，用所有的火源把地图处理完了之后再跑广搜

 

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int maxn=1050;
 8 const int inf=0x3f3f3f3f;
 9 struct node{
10     int x,y,t;
11     node(int X,int Y,int T)
12     {
13         x=X,y=Y,t=T;
14     }
15 };
16 queue<node> q;
17 int t,n,m,p[maxn][maxn],vis[maxn][maxn],sx,sy;
18 int dx[]={0,0,1,-1};
19 int dy[]={1,-1,0,0};
20 char a[maxn][maxn];
21 void init_bfs()
22 {
23     while(!q.empty())
24     {
25         node u=q.front();q.pop();
26         for(int i=0;i<4;i++)
27         {
28             int vx=u.x+dx[i],vy=u.y+dy[i];
29             if((vx>=1&&vx<=n&&vy>=1&&vy<=m)&&a[vx][vy]!='#'&&p[vx][vy]==inf)
30             {
31                 q.push(node(vx,vy,0));
32                 p[vx][vy]=p[u.x][u.y]+1;
33             }
34         }
35     }
36 }
37 void bfs()
38 {
39     while(!q.empty()) q.pop();
40     q.push(node(sx,sy,0));
41     vis[sx][sy]=1;
42     while(!q.empty())
43     {
44         node u=q.front();q.pop();
45         if(u.x==n||u.x==1||u.y==1||u.y==m)
46         {
47             printf("%d\n",u.t+1);
48             return;
49         }
50         for(int i=0;i<4;i++)
51         {
52             int vx=u.x+dx[i],vy=u.y+dy[i];
53             if((vx>=1&&vx<=n&&vy>=1&&vy<=m)&&a[vx][vy]!='#'&&!vis[vx][vy]&&(u.t+1<p[vx][vy]))
54             {
55                 q.push(node(vx,vy,u.t+1));
56                 vis[vx][vy]=1;
57             }
58         }
59     }
60     puts("IMPOSSIBLE");
61     return;
62 }
63 int main()
64 {
65     scanf("%d",&t);
66     while(t--)
67     {
68         while(!q.empty()) q.pop();
69         memset(vis,0,sizeof(vis));
70         memset(p,inf,sizeof(p));
71         scanf("%d%d",&n,&m);
72         for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
73         for(int i=1;i<=n;i++)
74             for(int j=1;j<=m;j++)
75             {
76                 if(a[i][j]=='J') sx=i,sy=j;
77                 if(a[i][j]=='F')
78                 {
79                     q.push(node(i,j,0));
80                     p[i][j]=0;
81                 }
82             }
83             init_bfs();
84             bfs();
85     }
86     return 0;
87 }