学步园

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

分析：最短路径，其实很简单的，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 %d\n", 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("%s\n", g[i]);
        if ( bfs() ) printf("%d\n", d[xa][ya]);
        else printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
}