题目链接:http://vjudge.net/contest/132239#problem/A
题目链接:https://uva.onlinejudge.org/external/116/11624.pdf
《训练指南》P307
分析:只需要预处理每个格子起火的时间,在BFS扩展节点的时候加一个判断,到达该节点的时候,格子没有起火。
写法很巧妙,两次BFS类似,数据加一维kind,表示Joe到达该点和火到达该点。
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int maxr = 1000+5; const int maxc = 1000+5; int R,C; char maze[maxr][maxc]; struct Cell{ int r,c; Cell (int r,int c) : r(r),c(c) {} }; const int dr[] = {-1,1,0,0}; const int dc[] = {0,0,-1,1}; int d[maxr][maxc][2] ,vis[maxr][maxc][2]; queue<Cell> Q; void bfs(int kind) { while(!Q.empty()) { Cell cell = Q.front(); Q.pop(); int r = cell.r, c = cell.c; for(int dir = 0; dir < 4; dir++) { int nr = r + dr[dir], nc = c + dc[dir]; if(nr >= 0 && nr < R && nc >= 0 && nc < C && maze[nr][nc] == '.' && !vis[nr][nc][kind]) { Q.push(Cell(nr, nc)); vis[nr][nc][kind] = 1; d[nr][nc][kind] = d[r][c][kind] + 1; } } } } int ans; void check(int r,int c) { if(maze[r][c]!='.'||!vis[r][c][0]) return; ///走不到 if(!vis[r][c][1]||d[r][c][0]<d[r][c][1]) ans= min(ans,d[r][c][0]+1); ///该点火到达不了,或者joe先于火 } int main() { //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&R,&C); int jr,jc; vector<Cell> fires; for(int i=0;i<R;i++) { scanf("%s",maze[i]); for(int j=0;j<C;j++) { if(maze[i][j]=='J') { jr = i; jc = j; maze[i][j] = '.'; } else if(maze[i][j]=='F') { fires.push_back(Cell(i,j)); maze[i][j] = '.'; } } } memset(vis,0,sizeof(vis)); ///各个点到joe的距离 ///Joe vis[jr][jc][0] = 1; d[jr][jc][0] = 0; Q.push(Cell(jr,jc)); bfs(0); for(int i = 0;i<fires.size();i++) { vis[fires[i].r][fires[i].c][1] = 1; d[fires[i].r][fires[i].c][1] = 0; Q.push(fires[i]); } bfs(1); ans = INF; for(int i=0;i<R;i++) { check(i,0); check(i,C-1); } for(int i=0;i<C;i++) { check(0,i); check(R-1,i); } if(ans==INF) printf("IMPOSSIBLE "); else printf("%d ",ans); } return 0; }