Fire! UVA

看了很多的博客，然而还是不懂第一遍的BFS_Fire中 if(mx<0||mx>=n||my<0||my>=m||map[mx][my]=='#'||tim[mx][my]!=-1) continue; 队列中第一个火遍历整个图后，剩下的火因为tim[ ][ ]除了墙的位置是-1，火的位置是0以外，都是正数，所以不会再一次遍历更新tim数组。。。我很好奇为什么能A~~~

惭愧，学艺不精啊！忽略了队列是先进先出的，所以将火的位置存入队列，那么每一个火在同一个时间段内（比如1秒，2秒，3秒。。。）都跑了一次；所以跑完整个队列，tim[ ][ ]就更新完了！数据结构用好了就是方便啊

这种情况：

.....
..J..
.###.
.#F#.
.###.
.....

J在外面，F被墙围着，所以可走的地方tim的值也是-1，所以 if(tim[mx][my]!=-1&&dis[p.first][p.second]+1>=tim[mx][my]) continue; 两个判定却一不可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 typedef pair<int,int> P;
 8 
 9 const int maxn=1005;
10 
11 int n,m,sx,sy;
12 int tim[maxn][maxn],dis[maxn][maxn];
13 char map[maxn][maxn];
14 
15 int dx[4]={1,0,-1,0};
16 int dy[4]={0,1,0,-1};
17 
18 void BFS_Fire()
19 {   queue<P> q;
20     memset(tim,-1,sizeof(tim));
21     for(int i=0;i<n;i++)
22         for(int j=0;j<m;j++) if(map[i][j]=='F') { tim[i][j]=0; q.push(make_pair(i,j)); }
23     while(q.size()){
24         P p=q.front();
25         q.pop();
26         
27         for(int i=0;i<4;i++){
28             int mx=dx[i]+p.first,my=dy[i]+p.second;
29             if(mx<0||mx>=n||my<0||my>=m||map[mx][my]=='#'||tim[mx][my]!=-1) continue;    //tim[mx][my]!=-1 相当于开了一个标记数组，挺实用的！
30             tim[mx][my]=tim[p.first][p.second]+1;
31             q.push(make_pair(mx,my));
32         }
33     }
34 }
35 
36 int BFS_man()
37 {   queue<P> q;
38     q.push(make_pair(sx,sy));
39     memset(dis,-1,sizeof(dis));
40     
41     dis[sx][sy]=0;
42     while(q.size()){
43         P p=q.front();
44         q.pop();
45         if(p.first==0||p.first==n-1||p.second==0||p.second==m-1) return dis[p.first][p.second];
46         for(int i=0;i<4;i++){
47             int mx=dx[i]+p.first,my=dy[i]+p.second;
48             if(mx<0||mx>=n||my<0||my>=m||map[mx][my]=='#'||dis[mx][my]!=-1) continue;
49             if(tim[mx][my]!=-1&&dis[p.first][p.second]+1>=tim[mx][my]) continue;              //为什么一定要tim[mx][my]!=-1?
50             dis[mx][my]=dis[p.first][p.second]+1;                                                      
51             q.push(make_pair(mx,my));                                                                  
52             /*  wrong!                                               
53             if(dis[p.first][p.second]+1<tim[mx][my]){                                                                                                 
54                 dis[mx][my]=dis[p.first][p.second]+1;                                                  
55                 q.push(make_pair(mx,my));
56             }
57             */
58             /*  wrong! 
59             dis[mx][my]=dis[p.first][p.second]+1;
60             if(dis[mx][my]<tim[mx][my]) q.push(make_pair(mx,my));
61             */
64         } 
65     }
66     return -1;
67 }
68 
69 int main()
70 {   int cases;
71     scanf("%d",&cases);
72     while(cases--){
73         scanf("%d%d",&n,&m);
74         getchar();
75         for(int i=0;i<n;i++){
76             gets(map[i]);
77             for(int j=0;j<m;j++) if(map[i][j]=='J') { sx=i, sy=j; } 
78         }
79         
80         BFS_Fire();
81         int ans=BFS_man();
82         if(ans==-1) cout<<"IMPOSSIBLE"<<endl;
83         else cout<<ans+1<<endl;
84     }
85     return 0;
86 }