題目：
這是mengxiang000和Tabris來到幼稚園的第四天，幼稚園老師在值班的時候突然發現幼稚園某處發生火災，而且火勢蔓延極快，老師在第一時間就發出了警報，位于幼稚園某處的mengxiang000和Tabris聽到了火災警報聲的同時拔腿就跑，不知道兩人是否能夠逃脫險境？ 幼稚園可以看成是一個N*M的圖，在圖中一共包含以下幾種元素： “.”:表示這是一塊空地，是可以随意穿梭的。 “#”：表示這是一塊牆，是不可以走到這上邊來的，但是可以被火燒毀。 “S”：表示mengxiang000和Tabris所在位子。 “E”：表示幼稚園的出口。 “*”表示火災發源地（保證輸入隻有一個火災發源地）。 已知每秒有火的地方都會向周圍八個格子（上下左右、左上、右上、左下、右下）蔓延火勢.mengxiang000和Tabris每秒都可以選擇周圍四個格子（上下左右）進行移動。（假設兩人這一秒行動完之後，火勢才蔓延開） 根據已知條件，判斷兩人能否成功逃脫險境,如果可以，輸出最短逃離時間，否則輸出T_T。
輸入描述:
第一行輸入一個整數t，表示一共的測試資料組數。 第二行輸入兩個整數n，m，表示幼稚園的大小。 接下來n行，每行m個字元，表示此格子是什麼元素。 t<=200 3<=n<=30 3<=M<=30 保證圖中有一個起點，一個出口，一個火災源處. 輸出描述:
每組資料輸出一行，如果兩人能夠成功到達出口，那麼輸出最短逃離時間，否則輸出T_T 示例1
輸入
3
5 5
*....
.....
..S#.
...E.
.....
5 5
...#*
..#S#
...##
....E
.....
5 5
.....
S....
..*#.
...E.
..... 輸出
2
T_T
T_T
解析：
這題乍一看挺簡單（确實挺簡單），但本人嘗試多次竟然沒有AC，異常難受~ o(TωT)o
一開始的思路（有誤，寫給自己的，可以略過）：存圖，然後将小盆友和火同時Bfs,嗯就是這裡出問題了，火焰和人的拓展條件并不一樣，是以，在入隊的數量并不同，SO拓展并不是同步的！！_φ(❐_❐✧ 人醜就要多WA
接着在網上找了個正解（https://www.cnblogs.com/zhgyki/p/9568761.html），理一下其思路：将火焰的拓展和人的拓展分隔開，先将火焰拓展，利用時間作為之後的比較中介，将火焰到達每個點的時間記錄在該點（這個思路如此牛*）。接着是人的Bfs,注意遇到出口時，時間小于或等于該點火焰蔓延到的時間即可（題目說明了火焰蔓延是後滞的），然後普通的逃脫到的點的時間要嚴格小于火焰到達的時間。
正解： 
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 using namespace std;
5 typedef long long ll;
6 #define maxn 35
7 #define Inf 0x7fffffff
8 int n=0,m=0,ans=Inf;
9 int t=0;
10 char Map[maxn][maxn];
11 bool vis[maxn][maxn]={0};
12 int fir[maxn][maxn]={0};//記錄fire到每一格所需時間
13 int dir[][2]={
14 {1,0},{-1,0},{0,1},{0,-1},
15 {1,1},{-1,-1},{-1,1},{1,-1}
16 };
17 struct Point{
18 int x,y,tm;
19 Point(){tm=0;}
20 Point(int a,int b,int c):x(a),y(b),tm(c){}
21 }fi,st;
22 void FireGo()
23 {
24 memset(vis,false,sizeof(vis));
25 memset(fir,0,sizeof(fir));
26 queue<Point> q;
27 q.push(fi);
28 vis[fi.x][fi.y]=true;
29 while(q.size())
30 {
31 Point head=q.front();
32 q.pop();
33 for(int i=0;i<8;++i)
34 {
35 int nx=head.x+dir[i][0];
36 int ny=head.y+dir[i][1];
37 if(nx<0||nx>=n||ny<0||ny>=m) continue;
38 if(vis[nx][ny]) continue;
39 vis[nx][ny]=true;
40 fir[nx][ny]=head.tm+1;//計算每個點有火勢蔓延到的時間
41 q.push({nx,ny,head.tm+1});
42 }
43 }
44 }
45 bool Bfs()
46 {
47 memset(vis,0,sizeof(vis));//重新初始vis數組
48 queue<Point> q;
49 q.push(st);
50 vis[st.x][st.y]=true;
51 while(q.size())
52 {
53 Point head=q.front();
54 q.pop();
55 for(int i=0;i<4;++i)
56 {
57 int nx=head.x+dir[i][0];
58 int ny=head.y+dir[i][1];
59 if(nx<0||nx>=n||ny<0||ny>=m) continue; //越界
60 if(vis[nx][ny]) continue;
61 if(Map[nx][ny]=='#') continue;
62 if(Map[nx][ny]=='E' &&head.tm+1<=fir[nx][ny])//先到出口，火才到
63 {
64 //vis[nx][ny]=true;
65 //q.push({nx,ny,head.tm+1}); continue;
66 ans=head.tm+1;
67 return true;
68 }
69 if(head.tm+1<fir[nx][ny]){//要嚴格小于,==時本秒結束火就到
70 vis[nx][ny]=true;
71 q.push({nx,ny,head.tm+1});
72 }
73
74 }
75 }
76 return false;
77 }
78 int main()
79 {
80 cin>>t;
81 while(t--)
82 {
83 cin>>n>>m;
84 for(int i=0;i<n;++i)
85 for(int j=0;j<m;++j)
86 {
87 cin>>Map[i][j];
88 if(Map[i][j]=='S'){
89 st.x=i; st.y=j;
90 }
91 else if(Map[i][j]=='*'){
92 fi.x=i; fi.y=j;
93 }
94 }
95 FireGo();
96 if(Bfs()) cout<<ans<<endl;
97 else cout<<"T_T"<<endl;
98 }
99 return 0;
100 } View Code
錯解： 1 #include <iostream> //不能将火 和人同時bfs()兩者的拓展條件不同，入隊的數量不同，導緻拓展不同步
2 #include <queue>
3 #include <cstring>
4 using namespace std;
5 int n=0,m=0;
6 char Map[30][30]={0};
7 bool vis[30][30]={0};
8 bool judge[30][30]={0};
9 struct Point{
10 int x,y,tm;
11 Point(){ x=0; y=0; tm=0; }
12 Point(int a,int b,int c){ x=a; y=b; tm=c; }
13 }fi,en,st;
14 int dir[][2]={
15 {0,1},{1,0},{0,-1},{-1,0},
16 {1,1},{-1,-1},{1,-1},{-1,1} //斜方向
17 };
18 bool Check(int x,int y)//該點8方都不能有火源才安全
19 {
20 for(int i=0;i<8;++i)
21 {
22 if(Map[x+dir[i][0]][y+dir[i][1]]=='*')
23 return false;
24 }
25 return true;
26 }
27 int bfs()//fire 和 人同時移動
28 {
29 memset(vis,false,sizeof(vis));
30 memset(judge,false,sizeof(judge));
31 queue<Point> q;
32 st.tm=0;
33 q.push(st);
34 vis[st.x][st.y]=true;
35 while(!q.empty())
36 {
37 Point head=q.front();
38 q.pop();
39 for(int i=0;i<4;++i) //四方向周遊
40 {
41 int nx=head.x+dir[i][0];
42 int ny=head.y+dir[i][1];
43 if(nx<0||nx>=n||ny<0||ny>=m) continue; //越界
44 if(Map[nx][ny]=='E') return (head.tm+1); //到達出口
45 if(vis[nx][ny]) continue;
46 if(Map[nx][ny]=='#'||Map[nx][ny]=='*') continue; //牆 火
47 if(!Check(nx,ny)) continue; //到達的點不安全
48 vis[nx][ny]=true;
49 q.push({nx,ny,head.tm+1});
50 }
51 if(q.empty()) return 0;
52 //火勢蔓延
53 for(int i=0;i<8;++i)//這裡出錯，火的蔓延也應要用到隊列不然其實并未伸展
54 {
55 int nx=fi.x+dir[i][0];
56 int ny=fi.y+dir[i][1];
57 judge[nx][ny]=true;
58 if(nx<0||nx>=n||ny<0||ny>=m) continue; //越界
59 if(judge[nx][ny]) continue;
60 if(Map[nx][ny]=='E') return 0; //出口被燒
61 Map[nx][ny]='*';
62 }
63 }
64 return 0;
65 }
66 int main()
67 {
68 int t=0;
69 cin>> t;
70 while(t--)
71 {
72 cin>> n>> m;
73 for(int i=0;i<n;++i)
74 for(int j=0;j<m;++j)
75 {
76 cin>> Map[i][j];
77 if(Map[i][j]=='E'){
78 en.x=i; en.y=j;
79 }
80 else if(Map[i][j]=='*'){
81 fi.x=i; fi.y=j;
82 }
83 else if(Map[i][j]=='S'){
84 st.x=i; st.y=j;
85 }
86 }
87 int temp=bfs();
88 if(temp) cout<<temp<<endl;
89 else cout<<"T_T"<<endl;
90 }
91 return 0;
92 } View Code