zoj 1649 Rescue_BFS
题意：
在N*M的图中，找出'r'到'a'的最少时间。其中每走一步需要花费一个时间单位，遇到守卫（'x'）,需要花费额外的一个时间单位来通过它。
思路：
BFS+优先队列（递增）来求解，代码写法和普通的A到B点求最短步数相同。
AC代码：10ms，C++
View Code #include<cstdio> // BFS + 优先队列，求少时间#include<cstring> // 遇到哨兵多花费一秒#include<queue>#include<algorithm>using namespace std;const int MAXN = 205;int dir[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };char Graph[MAXN][MAXN];int vis[MAXN][MAXN]; // 用来标记一走位置struct pos{ int x, y, step; bool operator<( pos t )const{ //优先队列递增排列 return t.step < step; } bool operator ==( pos t ){ return t.x == x && t.y == y; }}S, T;priority_queue< pos >Q;int row, col;void init(){ while( !Q.empty() )Q.pop(); memset( vis, 0, sizeof(vis) ); vis[S.x][S.y] = 1;}int BFS(){ init(); pos s, t; int i; Q.push( S ); while( !Q.empty() ) { s = Q.top(); Q.pop(); if( s == T )return s.step; for( i = 0; i < 4; i++ ) { t.x = s.x + dir[i][0]; t.y = s.y + dir[i][1]; if( t.x >=0 && t.x < row && t.y >= 0 && t.y < col && Graph[t.x][t.y] != '#' && !vis[t.x][t.y] ) { if( Graph[t.x][t.y] == 'x' ) t.step = s.step + 2; else t.step = s.step + 1; Q.push( t ); vis[t.x][t.y] = 1; } } } return -1;}int main(){ int i, j; while( ~scanf( "%d%d", &row, &col ) ) { for( i = 0; i < row; i++ ) { scanf( "%s", Graph[i] ); for( j = 0; j < col; j++ ) if( Graph[i][j] == 'a' ) S.x = i, S.y = j, S.step = 0; else if( Graph[i][j] == 'r' ) T.x = i, T.y = j; } int step = BFS(); if( step == -1 )printf( "Poor ANGEL has to stay in the prison all his life.\n"); else printf( "%d\n", step ); } return 0;}/*测试数据：7 8#.#####.#a.#xr..#.x#xx....xxxx.##........#..............7 8#.#####.#.a#..r.#..#x.....#..#.##...##...#..............*/这题使用优先代码可以很大程度上的减少代码复杂度。
这题也可以逆向搜索，从'a'到'r'。结果一样，如果遇到多起点，唯一终点的情况下，可以使用逆向搜索的方法。
TAG:
