UVALive - 8325 Barareh on Fire

本文主要是介绍UVALive - 8325 Barareh on Fire，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVALive - 8325 Barareh on Fire

题目链接

题目大意：
以一个样例来说明，

7 7 2
f------
-f---f-
----f--
-------
------f
---s---
t----f-

7 7代表图有7行7列。
图中，f表示该点有火，s表示起点，t表示终点，-为空地。

2表示火向四周蔓延一次所需要的时间为2秒，
火蔓延一次，会同时向8个方向蔓延，上下左右，左上，右上，左下，右下。

人每走一步只需要1秒，但只能够走上下左右四个方向。

问在不被火烧的情况下，人是否能够从起点走到终点，
可以的话找到一条最短的路，输出需要的最少步数，
不能的话，输出Impossible

挣扎的过程
开始，组队赛的时候，我们对bfs都不是很熟练，
但比赛到后面看到没有新的题被解出来，我们就试了一下。
思路：把地图的标记数组放在一个结构体里(我的理解是，人每走到一个点，那个点都会有一个标记数组)，然后跑一遍bfs。
结果：只过了一部分样例，后面又写了很多遍，写得比较乱，最后样例都没过。
（区别bfs/dfs的思想及实现）
get一个教训，不要写自己不是很熟练的东西，这样我们会有一种错觉，
觉得我们写的可能完全是错误的东西，自以为有可能会是对的。

比赛后我看了啊哈算法上bfs的部分，自己实现了一遍，样例是过了，但是runtime error/段错误，
我猜可能是结构体里的标记数组的原因，导致申请内存太多了？
（小插曲：csu上的样例输入，有一个多了一个空格，用string/%s输入都没啥事，
但我用%c就debug了差不多半小时，实力太菜，开始以为自己的程序有错误。
后面，在csu的校外交流群有图有真相的反映了一下，大佬隔天就修改了。）

后来，我把数组从结构体中拿了出来，又试了一遍，wrong answer。
（我当时的思路是，如果火可以蔓延的话，让火先蔓延，然后判断人是否可以继续前进。
可能出错的地方：入队/出队，前后火的分布可能会不一样。）

最后在网上爬了一篇大佬的博客。
大佬：
一个预处理的bfs，开始放在中间更新，写的超级麻烦还过不了，后来预处理过了。
根据判断这个点的八个方向是否有火来判断他是否会变成火，
不要根据有火来使四周的变成火，否则会出错。

（又是逆向思维吗？这样子都可以，厉害厉害
还有一个疑问，为什么“不要根据有火来使四周的变成火，否则会出错”？
自我感觉是一样的）

ac代码

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;#define maxn 105int n, m, k, sx, sy, ex, ey;
int vis[maxn][maxn], mapn[maxn][maxn][maxn];
int dx[] = { 0, 0, 1, -1 }, dy[] = { 1, -1, 0, 0};
int tx[] = { 0, 0, 1, -1, 1, 1, -1, -1 }, ty[] = { 1, -1, 0, 0, 1, -1, 1, -1 };struct
node {int step, x, y;
};void
bfs() {node p;p.x = sx, p.y = sy, p.step = 0;vis[sx][sy] = 1;queue<node> q;q.push(p);while( !q.empty() ) {node now = q.front();q.pop();if( now.x == ex && now.y == ey ) {cout << now.step << endl;return ;}for( int i = 0; i < 4; i ++ ) {int xx = now.x + dx[i];int yy = now.y + dy[i];if( xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && mapn[(now.step+1)/k][xx][yy] ) {// 只考虑当前的情况step// 如果我要往下走一步，我只要根据当前的情况计算出下一步我是否可走// 下一秒的图，可能并不完全包含上一秒的图// 考虑：上一秒的图有一个点有火，且四周都没有火，则下一秒的图对应这个点不会有火node tmp;tmp.x = xx, tmp.y = yy, tmp.step = now.step + 1;q.push(tmp);vis[xx][yy] = 1;}}}cout << "Impossible" << endl;
}int
main() {while( cin >> n >> m >> k ) {if( !n && !m && !k ) {break;}memset( vis, 0, sizeof(vis) );for( int i = 0; i < n; i ++ ) {for( int j = 0; j < m; j ++ ) {char t;cin >> t;if( t == 's' ) {  // 空地为1，火苗为0mapn[0][i][j] = 1;sx = i, sy = j;} else if( t == 't' ) {mapn[0][i][j] = 1;ex = i, ey = j;} else if( t == '-' ) {mapn[0][i][j] = 1;} else if( t == 'f' ){mapn[0][i][j] = 0;}}}//预处理for( int p = 1; p < max( n, m ); p ++ ) {  // p是什么意思？火最多向外蔓延的次数for( int i = 0; i < n; i ++ ) {for( int j = 0; j < m; j ++ ) {mapn[p][i][j] = 1;  // 全为1，没火for( int z = 0; z < 8; z ++ ) {int xx = i + tx[z];int yy = j + ty[z];if( xx >= 0 && xx < n && yy >= 0 && yy < m && !mapn[p-1][xx][yy] ) {mapn[p][i][j] = 0;// 遍历图中的每一个点// 只要下一层(上一秒)，8个中有1个方向有火，就会蔓延过来}}}}}bfs();}return 0;
}

数组不在结构体中

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;int book[105][105];typedef
struct {int x;int y;int s;
}Node;int
main() {queue <Node> q;Node cur, next;char c;int d[8][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0},{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};int n, m, k, i, j, p, startx, starty, endx, endy, flag;while( scanf("%d %d %d", &n, &m, &k) && n && m && k) {getchar();  //memset(book, 0, sizeof(book));for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {scanf("%c", &c);if( c == 'f' ) {book[i][j] = 1;}else if( c == 's' ) {startx = i;starty = j;}else if( c == 't' ) {endx = i;endy = j;}}getchar();  //}/*for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {printf("%d", book[i][j]);}printf("\n");}*/cur.x = startx;cur.y = starty;cur.s = 0;book[startx][starty] = 1;q.push(cur);flag = 0;while( !q.empty() ) {next = cur = q.front();  //q.pop();if( k == 1 || (cur.s != 0 && cur.s % k == 0) ) {  //for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {if( book[i][j] == 1 ) {for( p = 0; p < 8; p++ ) {next.x = book[i][j] + d[p][0];  //next.y = book[i][j] + d[p][1];if( next.x < 1 || next.x > n || next.y < 1 || next.y > m ) {continue;}book[next.x][next.y] = 1;}}}}}/*for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {printf("%d", book[i][j]);}printf("\n");}*/for( p = 0; p < 4; p++ ) {next.x = cur.x + d[p][0];next.y = cur.y + d[p][1];if( next.x < 1 || next.x > n || next.y < 1 || next.y > m ) {continue;}if( book[next.x][next.y] == 0 ) {  // 没有fire，往外推一层book[next.x][next.y] = 1;next.s = cur.s + 1;q.push(next);}if( next.x == endx && next.y == endy ) {flag = 1;if( next.s != 0 ) {  //printf("%d\n", next.s);}break;}}if( flag == 1 ) {while( !q.empty() ) {q.pop();}break;}}if( flag == 0 || next.s == 0 ) {  // 到不了终点/在原地printf("Impossible\n");}}return 0;
}

数组在结构体中

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;typedef
struct {int x;int y;int s;int book[105][105];  // 标记fire，有fire为1
}Node;int
main() {queue <Node> q;Node cur, next;char c;int d[8][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0},{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};int n, m, k, i, j, p, startx, starty, endx, endy, flag;while( scanf("%d %d %d", &n, &m, &k) && n && m && k) {getchar();  //memset(cur.book, 0, sizeof(cur.book));for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {scanf("%c", &c);if( c == 'f' ) {cur.book[i][j] = 1;}else if( c == 's' ) {startx = i;starty = j;}else if( c == 't' ) {endx = i;endy = j;}}getchar();  //}/*for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {printf("%d", cur.book[i][j]);}printf("\n");}*/cur.x = startx;cur.y = starty;cur.s = 0;cur.book[startx][starty] = 1;q.push(cur);flag = 0;while( !q.empty() ) {next = cur = q.front();  //q.pop();if( k == 1 || (cur.s != 0 && cur.s % k == 0) ) {  //for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {if( cur.book[i][j] == 1 ) {for( p = 0; p < 8; p++ ) {next.x = cur.book[i][j] + d[p][0];  //开始我们可能这里错了？next.y = cur.book[i][j] + d[p][1];if( next.x < 1 || next.x > n || next.y < 1 || next.y > m ) {continue;}next.book[next.x][next.y] = 1;}}}}}/*for( i = 1; i <= n; i++ ) {for( j = 1; j <= m; j++ ) {printf("%d", next.book[i][j]);}printf("\n");}*/for( p = 0; p < 4; p++ ) {next.x = cur.x + d[p][0];next.y = cur.y + d[p][1];if( next.x < 1 || next.x > n || next.y < 1 || next.y > m ) {continue;}if( next.book[next.x][next.y] == 0 ) {  // 没有fire，往外推一层next.book[next.x][next.y] = 1;next.s = cur.s + 1;q.push(next);}if( next.x == endx && next.y == endy ) {flag = 1;if( next.s != 0 ) {  //printf("%d\n", next.s);}break;}}if( flag == 1 ) {break;}}if( flag == 0 || next.s == 0 ) {  // 到不了终点/在原地printf("Impossible\n");}}return 0;
}