杭電 HDU 1242 Rescue

限制及剪枝：
1、牆不能走，不能離開牢房范圍
2、殺死一個警衛要多花一秒鐘
3、當前步驟大於等於最短時間時不用繼續再走（剪枝）
4、每次到達天使處要更新最短時間
5、不能走重復路（算剪枝把）          //這個也要說？？？囧。。。

AC代碼：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

#define MAX 999999

using namespace std;

struct Node
{
    int x,y;
    int time;
};

char map[210][210];
int st[210][210];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,mintime;

void Bfs(Node p)
{
    Node now,next;
    queue<Node> q;
    int i;
    q.push(p);
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        if(now.time >= mintime)       //剪枝，超過最短時間的不用再走了
        {
            break;
        }
        if(map[now.x][now.y] == 'a')  //找到天使時更新最短步驟
        {
            if(now.time < mintime)
            {
                mintime = now.time;
            }
        }
        if(map[now.x][now.y] == 'x')  //如果當前為門衛則多花1秒來殺死他
        {
            now.time += 1;
        }
        st[now.x][now.y] = 2;         //標記此路徑已經到達
        next.time = now.time + 1;     //下一步的時間加一
        for(i = 0; i < 4; i++)
        {
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];
            if(map[next.x][next.y] != '#' && st[next.x][next.y] == 0)
            {
                st[next.x][next.y] = 1;   //標記此路徑已經入隊
                q.push(next);
            }
        }
    }
    return ;
}

int main()
{
    int i,j;
    Node now;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(map,'#',sizeof(map));  //初始化全為牆
        memset(st,0,sizeof(st));      //初始化所有路徑均未走過
        mintime = MAX;
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j <= m; j++)
            {
                cin >> map[i][j];
                if(map[i][j] == 'r')
                {
                    now.x = i;
                    now.y = j;
                    now.time = 0;
                }
            }
        }
        Bfs(now);
        if(mintime == MAX)
        {
            printf("Poor ANGEL has to stay in the prison all his life.\n");
        }
        else
        {
            printf("%d\n",mintime);
        }
    }

    return 0;
}