题意：帮助joe走出一个大火蔓延的迷宫，其中joe每分钟可往上下左右四个方向之一走，所有着火的格子都会蔓延（空格与着火格有公共边，下一分钟这个空格也会着火）。迷宫中有一些障碍格，joe和火都无法进入，当joe走到一个边界的格子我们认为他走出了迷宫
输出R行C列的迷宫，#表示墙，.表示空地，J表示joe，F是着火格
如果能走出，输出最少时间否则，impossible
感觉很经典的一个问题,在处理每个点着火的时间的时候，却发现假若当前这个点之前已经被火着过一次怎么办了，在一想这就是简单的bfs最优性质决定的，用宽搜的时候就已经保证了在搜索过的着火点已经是最优的了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
using namespace std;
typedef long long ll;
const int maxn=(int)1e3+10;
char map[maxn][maxn];
int step[maxn][maxn];
int vis[maxn][maxn];
int n,m;
ll inf=0x3f3f3f3f;
int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
queue<pair<int,int> >q;
void clear(queue<pair<int,int> >& q){
queue<pair<int,int> > empty;
swap(empty,q);
}
void bfs_fire(){
while(!q.empty()){
pair<int,int> p=q.front();
q.pop();
int x=p.first,y=p.second;
// vis[x][y]=1;//vis[p.first][p.second]=1; 如果一直用first second去查找肯定会耗费时间
pair<int,int> tmp;
for(int i=0;i<4;++i){
int dx=x+dir[i][0];
int dy=y+dir[i][1];
if(dx<1||dx>n||dy<1||dy>m||step[dx][dy]!=inf)continue;
if(map[dx][dy]=='#')continue;
tmp.first=dx,tmp.second=dy;
step[dx][dy]=step[x][y]+1;
q.push(tmp);
}
}
}
int pe[maxn][maxn];
void bfs_person(){
pair<int,int > p;
while(!q.empty()){
p=q.front();
q.pop();
int x=p.first,y=p.second;
if(x==1||x==n||y==1||y==m){
printf("%d\n",pe[x][y]+1);
return ;
}
// vis[x][y]=1;
for(int i=0;i<4;++i){
int dx=x+dir[i][0];
int dy=y+dir[i][1];
if(dx<1||dx>n||dy<1||dy>m||pe[dx][dy]!=inf)continue;
if(map[dx][dy]=='#')continue;
if( (pe[x][y]+1<step[dx][dy]) ){//&&step[dx][dy]!=inf wa
//加上这个！=inf开始是为了防止更新到障碍物所在的方格，其实上面的！=#已经判断了，不加也可以，不过加上他之后竟然wa掉，那就是说存在数据火到不了的网格人可以到，障碍物把火源包围了的这种情况
pe[dx][dy]=pe[x][y]+1;
q.push(make_pair(dx,dy));
}
}
}
printf("IMPOSSIBLE\n");return ;
}
void solve(){
memset(step,inf,sizeof(step));
//memset(vis,0,sizeof(vis));
while(!q.empty())q.pop();
//clear(q);
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j)
// cout<<map[i][j];
// cout<<endl;
// }
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(map[i][j]=='F'){
step[i][j]=0;
q.push(make_pair(i,j));
}
}
bfs_fire();
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j){
// cout<<step[i][j]<<' ';
// }
// cout<<endl;
// }
// memset(vis,0,sizeof(vis));
memset(pe,inf,sizeof(pe));
// clear(q);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(map[i][j]=='J'){
pe[i][j]=0;
q.push(make_pair(i,j));
break;
}
}
bfs_person();
// for(int i=1;i<=n;++i){
// for(int j=1;j<=m;++j)
// cout<<pe[i][j]<<' ';
// cout<<endl;
// }
//return;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",(map[i]+1));
}
solve();
}
return 0;
}
//除了上面的那个inf问题还有就是开始定义了两个vis的初始化，一开始就T掉，
uva11624Fire!
-------------本文结束感谢您的阅读-------------