题目大意:在一个N*M的迷宫内,J代表某人(只有一个),F代表火(可能不只一个),#代表墙,火每分钟会向四周除了墙以外的地方扩散一层,问人能否在没被火烧到
之前逃出迷宫,若能逃出输出最短时间。很明显的bfs。但由于火到达的地方人不能抵达,故需先对火进行bfs,标记后若人在火烧到之前抵达即可。最后逃出时间需要加一,
因为当时只是抵达边界,若逃出时间需加一。
#include <stdio.h> #include <queue> #include <string.h> #include <algorithm> using namespace std; #define oo 0x3f3f3f3f int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int m, n, time[1005][1005], vis[1005][1005]; char maps[1005][1005]; struct point { int x, y, step; }; point start; queue<point>Fire; void Fire_time() { point now, next; while(Fire.size()) { now = Fire.front(); Fire.pop(); time[now.x][now.y] = now.step; for(int i=0; i<4; i++) { next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; next.step = now.step + 1; if(next.x>=0 && next.x<m && next.y>=0 && next.y<n && !vis[next.x][next.y] && maps[next.x][next.y]!='#') { vis[next.x][next.y] = 1; Fire.push(next); } } } } int bfs() { queue<point>Q; Q.push(start); memset(time, oo, sizeof(time)); Fire_time(); memset(vis, 0, sizeof(vis)); point now, next; while(Q.size()) { now = Q.front(); Q.pop(); if(now.x==m-1 || now.y==n-1 || now.x==0 || now.y==0)return now.step+1; for(int i=0; i<4; i++) { next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; next.step = now.step + 1; if(next.x>=0 && next.x<m && next.y>=0 && next.y<n && !vis[next.x][next.y] && maps[next.x][next.y]=='.' && next.step<time[next.x][next.y]) { vis[next.x][next.y] = 1; Q.push(next); } } } return -1; } int main() { int Text; scanf("%d", &Text); while(Text--) { scanf("%d %d", &m, &n); memset(vis, 0, sizeof(vis)); for(int i=0; i<m; i++) scanf("%s", maps[i]); for(int i=0; i<m; i++) for(int j=0; j<n; j++) { if(maps[i][j]=='J') { start.x = i; start.y = j; start.step = 0; } if(maps[i][j]=='F') { point s; s.x = i; s.y = j; s.step = 0; Fire.push(s); vis[i][j] = 1; } } int ans = bfs(); if(ans==-1)printf("IMPOSSIBLE "); else printf("%d ", ans); } return 0; }