ZOJ 1649 Rescue （BFS）

题目大意：在一个矩阵里，有五种字符，一种是起点，一种是终点，一种代表墙不能走的，一种代表警卫需要花时间杀警卫的，最后一种代表路，每走一个格要花一个单位时间，杀一个警卫要花一个单位时间。求从起点到终点，花得最短时间！

分析：最短路径，其实很简单的，bfs搜索，然后判断一下是不是墙，是不是警卫和路，分别处理；在用一个数组d来记录每个点到起点的最短路径，同时也是用来标记已经遍历过的状态。

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 210;
const int M = 210;
const int INF = 1000000;
int n, m, xa, ya, xr, yr, d[N][M], x[4] = { 0, 0, 1, -1 }, y[4] = { 1, -1, 0, 0 };
bool vis[N][N];
char g[N][M];
struct P { int x, y; };
bool bfs() {
queue<P> Q;
P e;
e.x = xr, e.y = yr;
Q.push( e );
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= m; ++j ) d[i][j] = INF;
d[xr][yr] = 0;
while ( !Q.empty() ) {
P u = Q.front(); Q.pop();
int ux = u.x , uy = u.y;
//printf("%d %dn", ux, uy);
for ( int i = 0; i < 4; ++i ){
int x1 = u.x + x[i], y1 = u.y + y[i];
if ( g[x1][y1] == '#' ) continue;
if ( g[x1][y1] == 'x' ) {
if ( d[x1][y1] > d[ux][uy] + 2 ) {
d[x1][y1] = d[ux][uy] +2 ;
e.x = x1, e.y = y1;
Q.push(e);
}
}
else if ( g[x1][y1] == '.' || g[x1][y1] == 'a' ) {
if ( d[x1][y1] > d[ux][uy] + 1 ) {
d[x1][y1] = d[ux][uy] + 1;
e.x = x1; e.y = y1;
Q.push(e);
}
}
}
}
if ( d[xa][ya] == INF ) return false;
else return true;
}
int main()
{
while ( scanf("%d%d", &n, &m) != EOF ) {
getchar();
memset(vis, 0, sizeof(vis));
for ( int i = 0; i <= m+1; ++i ) g[i][0] = g[i][m+1] = '#';
for ( int i = 0; i <= n+1; ++i ) g[0][i] = g[n+1][i] = '#';
for ( int i = 1; i <= n; ++i, getchar() )
for ( int j = 1; j <= m; ++j ) {
scanf("%c", &g[i][j]);
if ( g[i][j] == 'a' ) xa = i, ya = j;
if ( g[i][j] == 'r' ) xr = i, yr = j;
}
//for ( int i = 0; i <= m + 1; ++i ) printf("%sn", g[i]);
if ( bfs() ) printf("%dn", d[xa][ya]);
else printf("Poor ANGEL has to stay in the prison all his life.n");
}
}

最后

以上就是高贵睫毛为你收集整理的ZOJ 1649 Rescue （BFS）的全部内容，希望文章能够帮你解决ZOJ 1649 Rescue （BFS）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。