UVA11624 Fire! （BFS）

题目链接：洛谷：或者这里：Vjudge更方便

题目大意：火在蔓延，人在走。火会蔓延，不会熄灭，我们可以确定某个点着火的时间（广搜）。对于J来说，要是他走到某点的时间比火蔓延到该点的时间要短，那么他走到该点的时候，火还没蔓延过来，他就可以走到该点，否则，不能进入该点。

思路：WA了一页开始是因为 不知道火可以有多把，然后之后的一页就不知道为啥WA，调调竟然过了，

1）先把所有的火跑一遍图，然后用一个二维数组存下来火跑到每个点的距离

2）之后再让人走，如果人走的这一步 小于 火走到这里所用的时间，就可以继续走，

3）退出条件，当人在迷宫的边上的时候，下一步就可以逃生了。

AC代码：

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1009;int n, m;
char maze[maxn][maxn];
bool vis[maxn][maxn];
int dist[maxn][maxn];int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, 1, -1};
struct node{int x, y;int step;node(){step = 0;}
};
bool check(node now){if(now.x <= n && now.x > 0 && now.y > 0 && now.y <= m){return 1;}return 0;
}
void FireBFS(node fire[], int all){queue q;for(int i = 0; i < all; i++){q.push(fire[i]);}node front, next;while(!q.empty()){front = q.front();q.pop();for(int i = 0; i < 4; i++){next.x = front.x + X[i];next.y = front.y + Y[i];if( !vis[next.x][next.y] && check(next) && maze[next.x][next.y] != '#'){next.step = front.step + 1;vis[next.x][next.y] = 1;dist[next.x][next.y] = next.step;q.push(next);}}}
}
int BFS(node start){memset(vis, 0, sizeof(vis));vis[start.x][start.y] = 1;queue q;while(!q.empty()) q.pop();q.push(start);node front, next;while(!q.empty()){front = q.front();q.pop();if(front.x == 1 || front.x == n || front.y == 1 || front.y == m){return front.step + 1;}for(int i = 0; i < 4; i++){next.x = front.x + X[i];next.y = front.y + Y[i];next.step = front.step + 1;if( !vis[next.x][next.y] && maze[next.x][next.y] != '#' && check(next)){if(dist[next.x][next.y] > next.step){vis[next.x][next.y] = 1;q.push(next);}}}}return -1;
}
int main(){int T;cin >> T;while(T--){node start, fire[maxn];cin >> n >> m;int q = 0;memset(vis, 0, sizeof(vis));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> maze[i][j];dist[i][j] = 9999;if(maze[i][j] == 'J'){start.x = i;start.y = j;	}if(maze[i][j] == 'F'){fire[q].x = i;fire[q].y = j;dist[i][j] = 0;vis[i][j] = 1;q++;}}}FireBFS(fire, q); 
//		for(int i = 1; i <= n; i ++){
//			for(int j = 1; j <= m; j++){
//				cout << dist[i][j] << " " ;
//			}
//			cout << endl;
//		}int ans = BFS(start);if(ans == -1){cout << "IMPOSSIBLE" << endl;}else{cout << ans << endl;}}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！