1101: 着火的房间
题目描述
救救PIPI！！PIPI被关在一个着火的房间里了！
该房间中有 nxm 个位置， 用一个字符矩阵表示。
‘s’ 代表PIPI的起点位置。
‘t’ 代表出口位置。
‘f’ 代表房间的着火点。
‘-’ 代表房间还未着火的点。
房间里面有若干个着火点，每个着火点的移动速率是k , 意思是若一个位置在 x 时刻起火了，那么在 x+k 时刻它周围8个方向都会起火。
PIPI每秒能够移动到上下左右四个方向中的一个未着火的位置。
请你编程计算可怜的PIPI能否成功逃离这个房间，如果PIPI能够成功逃离这个房间，输出PIPI逃出房间的最短时间，如果PIPI不能逃出这个房间，输出"Impossible"。
输入
输入包含多组测试用例。
对于每一组测试用例，输入第一行包含三个整数 n,m,k .分别代表房间位置的行数，列数，以及着火点的移动速率。(1<=n,m,k<=100)
接下来输入一个n*m的字符矩阵，代表房间在0时刻的状态。
以0 0 0 代表输入结束。
输出
对于每组样例，输出一行。如果PIPI能够成功逃离这个房间，输出PIPI逃出房间的最短时间，如果PIPI不能逃出这个房间，输出"Impossible"。
样例输入
7 7 2
f------
-f---f-
----f--
-------
------f
---s---
t----f-
3 4 1
t--f
--s-
----
2 2 1
st
f-
2 2 2
st
f-
0 0 0
样例输出
4
Impossible
Impossible
1
思路 1
两次 BFS，第一次 BFS 预处理出各个位置着火的时间，第二次 BFS 计算能否逃出房间。
#include<bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
char a[N][N];
int dir[8][2] = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}, {
-1, -1}, {
-1, 1}, {
1, -1}, {
1, 1}};
int fire[N][N];//预处理每个位置着火的时间
bool vis[N][N];
typedef struct Node
{
int x, y, t;
}node;
int main()
{
// freopen("in.cpp","r", stdin);int n, m, k;while(scanf("%d%d%d", &n, &m, &k) && (n || m || k)){
memset(vis, false, sizeof(vis));memset(fire, 0x7f, sizeof(fire));queue<node> q;node s, t;for(int i = 0; i < n; i++){
scanf("%s", a[i]);for(int j = 0; j < m; j++){
if(a[i][j] == 'f'){
q.push({
i, j, 0});fire[i][j] = 0;vis[i][j] = true;}else if(a[i][j] == 's')s = {
i, j, 0};else if(a[i][j] == 't')t = {
i, j, 0};}}node p;// 获取房间内各个位置着火的时间 while(!q.empty()){
p = q.front();q.pop();for(int i = 0; i < 8; i++){
int x = p.x + dir[i][0], y = p.y + dir[i][1];if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]){
fire[x][y] = p.t + k;vis[x][y] = true;q.push({
x, y, p.t + k});}}}q.push(s);memset(vis, false, sizeof(vis));vis[s.x][s.y] = true;while(!q.empty()){
p = q.front();q.pop();if(p.x == t.x && p.y == t.y){
t.t = 1;break;}for(int i = 0; i < 4; i++) {
int x = p.x + dir[i][0], y = p.y + dir[i][1], t = p.t + 1;if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && t < fire[x][y]){
q.push({
x, y, t});vis[x][y] = true;}}}if(t.t == 1)printf("%d\n", p.t);else puts("Impossible");}return 0;
}
思路 2
双向 BFS：模拟火和人同时移动，注意人不能走自己和火走过的地方，火不能走火走过的地方，因此要有不同的标记。用一个变量记录时间，当时间是k的倍数时，就让火走一步，而人是一直在走的。
#include<bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
char a[N][N];
int dir[8][2] = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}, {
-1, -1}, {
-1, 1}, {
1, -1}, {
1, 1}};
int vis[N][N];// 1-人走过，2-火走过
typedef struct Node
{
int x, y, t;
}node;
int main()
{
// freopen("in.cpp","r", stdin);int n, m, k, len;while(scanf("%d%d%d", &n, &m, &k) && (n || m || k)){
memset(vis, 0, sizeof(vis));queue<node> q1, q2;// q1--火，q2--人 node t, p;for(int i = 0; i < n; i++){
scanf("%s", a[i]);for(int j = 0; j < m; j++){
if(a[i][j] == 'f'){
q1.push({
i, j, 0});vis[i][j] = 2;}else if(a[i][j] == 's')q2.push({
i, j, 0});else if(a[i][j] == 't')t = {
i, j, 0};}}int now = 1;//记录当前时间while(!q2.empty()){
// 当时间为 k 的整数倍时，火走 if(now % k == 0){
len = q1.size();while(len--){
p = q1.front();q1.pop();for(int i = 0; i < 8; i++){
int x = p.x + dir[i][0], y = p.y + dir[i][1];if(x >= 0 && x < n && y >= 0 && y < m && vis[x][y] != 2){
vis[x][y] = 2;q1.push({
x, y, now});}}}}// 人走len = q2.size();while(len--){
p = q2.front();q2.pop();// 找到出口，标记，跳出循环if(p.x == t.x && p.y == t.y){
t.t = 1;break;}for(int i = 0; i < 4; i++){
int x = p.x + dir[i][0], y = p.y + dir[i][1];if(x >= 0 && x < n && y >= 0 && y < m && vis[x][y] == 0){
vis[x][y] = 1;q2.push({
x, y, now});}}}if(t.t == 1)break;now++;}if(t.t == 1)printf("%d\n", p.t);elseputs("Impossible");}return 0;
}