ACM-BFS之Rescue——hdu1242

13

用到优先队列的广搜，题意就是从r出发到a结束：

‘.‘是路，‘#‘是墙，‘x‘是卫兵，遇到.花费1s，遇到x花费2s。

求最短步数，若无法到达，输出-1。

BFS题目，这里用到了优先队列，vis数组存的是到达某一点的最短步数，而不是是否访问过这一点。

现在都有点不懂：题目中 "r" stands for each of Angel‘s friend. 和Angel‘s friends want to save Angel. Their task is: approach Angel.

我一直以为一张地图里的r有多个。。

事实证明好像r是只有一个。。。o(╯□╰)o啊

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int n,m,f_x,f_y,dis[4][2]={0,1,0,-1,1,0,-1,0};
char mapp[201][201];
int vis[201][201];
struct  Coordinate
{
    int x,y,step;
    friend bool operator<(Coordinate c1,Coordinate c2)
    {
        return c2.step<c1.step;
    }
}coor[1001];

// 判断当前点是否越界或碰墙
bool judge(int x,int y)
{
    if(x<0 || y<0 || x>=n || y>=m)  return 0;
    if(mapp[x][y]==‘#‘)    return 0;
    return 1;
}

// bfs用优先队列来做
int bfs(int x,int y)
{
    memset(vis,0,sizeof(vis));
    priority_queue <Coordinate>  q;
    Coordinate pre,lst;
    int i;

    pre.x=x;
    pre.y=y;
    pre.step=0;

    q.push(pre);

    while(!q.empty())
    {
        pre=q.top();
        q.pop();
        if(pre.x==f_x && pre.y==f_y)    return pre.step;

        for(i=0;i<4;++i)
        {
            lst.x=pre.x+dis[i][0];
            lst.y=pre.y+dis[i][1];

            if(judge(lst.x,lst.y))
            {
                // 判断当前点是否有卫兵，有则增加步数
                if(mapp[lst.x][lst.y]==‘x‘) lst.step=pre.step+2;
                else    lst.step=pre.step+1;
                
                // vis存到达该点最短步数
                if(vis[lst.x][lst.y]>=lst.step || vis[lst.x][lst.y]==0)
                {
                    vis[lst.x][lst.y]=lst.step;
                    q.push(lst);
                }
            }
        }
    }
    return -1;
}

int main()
{
    int i,j,s_x,s_y;
    int temp;
    while(cin>>n>>m)
    {
        for(i=0;i<n;++i)
            for(j=0;j<m;++j)
            {
                cin>>mapp[i][j];
                if(mapp[i][j]==‘r‘) {s_x=i;s_y=j;}
                if(mapp[i][j]==‘a‘) {f_x=i;f_y=j;}
            }

        temp=bfs(s_x,s_y);

        if(temp==-1)    cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
        else    cout<<temp<<endl;
    }
    return 0;
}

ACM-BFS之Rescue——hdu1242,布布扣,bubuko.com

ACM-BFS之Rescue——hdu1242

原文：http://blog.csdn.net/lttree/article/details/23259863