题目:一个平面迷宫中有一个人,迷宫中有些点起火了,火和人每个单位时间只能向相邻的格子移动,
其中有一些空间被墙壁占据,问这个人在不背或烧到的情况下,离开迷宫的最快时间。
分析:搜索。迷宫中的最短路,首先就会想到bfs;并且bfs利用队列会使状态空间按时间顺序分层。
而火的扩散过程正好符合这个时间的层次。所以我们会想到,利用两个队列,一个储存人的状态,
一个储存火的状态。按照时间顺序,先更新火蔓延的节点,再扩展人能到达的节点。
通过分析,我们发现这两个队列可以合并,只须初始化的时候,按照火节点然后是人的顺序入队即可。
(节点中加入一个是否是火节点的判断,就可以两种节点按不同的细节处理)
注意:时间是指走出迷宫的时间,到达边界后要加1;初始节点的判断。
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; char maps[1005][1005]; int step[1005][1005]; int d[4][2] = {1,0,-1,0,0,1,0,-1}; typedef struct nodep { int x,y,s,f; nodep( int X, int Y, int S, int F ){x = X;y = Y;s = S;f = F;} nodep(){} }point; point Q[1000005]; void bfs( int n, int m ) { int move = 0,save = 0; point J; for ( int i = 0 ; i < n ; ++ i ) for ( int j = 0 ; j < m ; ++ j ) { if ( maps[i][j] == ‘J‘ ) J = point( i, j, 0, 0 ); if ( maps[i][j] == ‘F‘ ) Q[save ++] = point( i, j, 0, 1 ); step[i][j] = 1000005; } step[J.x][J.y] = 0; Q[save ++] = J; while ( move < save ) { point New,now = Q[move ++]; if ( !now.f ) if ( now.x == 0 || now.x == n-1 || now.y == 0 || now.y == m-1 ) { printf("%d\n",now.s+1); return; } for ( int i = 0 ; i < 4 ; ++ i ) { New.x = now.x + d[i][0]; New.y = now.y + d[i][1]; New.s = now.s + 1; New.f = now.f; if ( New.x >= 0 && New.x < n && New.y >= 0 && New.y < m ) if ( maps[New.x][New.y] == ‘.‘ ) if ( New.f ) { maps[New.x][New.y] = ‘F‘; Q[save ++] = New; }else if ( step[New.x][New.y] > step[now.x][now.y] + 1 ) { step[New.x][New.y] = step[now.x][now.y] + 1; Q[save ++] = New; } } } printf("IMPOSSIBLE\n"); } int main() { int c,n,m; while ( scanf("%d",&c) != EOF ) while ( c -- ) { scanf("%d%d",&n,&m); for ( int i = 0 ; i < n ; ++ i ) scanf("%s",maps[i]); bfs( n, m ); } return 0; }
UVa 11624 - Fire!,布布扣,bubuko.com
原文:http://blog.csdn.net/mobius_strip/article/details/21531719