n-14 题解

有收获多多点赞，嘻嘻嘻
被这个多组输入恶心到了，根本没讲清楚是不是多组输入，害我多wa了两发
解题核心；当然是大家都熟悉的bfs，然后加上一点点贪心
其实我觉得这个都有点象A * 算法了，但是其实不是，远没有A * 算法复杂，也不需要设估价方程，也就是把普通队列换成了优先队列，其中的cmp需要自己写一下；
题意：很经典的搜索题题面，但是加上了一个警卫，警卫需要多花费一些时间，那么我们如果绕开警卫的话会不会有可能比不绕开要来的快？
当然可能的，例如下面举例
5 4
. . a .
. . x .
. . x .
. . x .
. . s .
如果直接杀过去所花费的时间为7，但是如果绕开，时间花费就只有七
所以我们需要加一个条件来设置优先级
所以很明显，这个条件就是当前时间越短的越先走下一步
这个时候就可以利用到stl的优先队列了，结构体优先队列，所以cmp就需要自己写一下了；
优先队列的cmp如下

struct node{
    int x,y;
    int dis;
};
struct cmp1    //另辟struct，排序自定义
{
    bool operator () (const node & a,const node & b) const
    {
       return b.dis<a.dis;//不管第几步了，只要时间短就优先；
    }
};
priority_queue <node,vector<node>,cmp1> s;

不过需要注意到优先队列是s.top（）/而不是s.front()；
接下来就是经典的bfs了
AC代码贴上
多组输入！多组输入！千万记得更新数组

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
char map[300][300];
struct node{
    int x,y;
    int dis;
};
struct cmp1    //另辟struct，排序自定义
{
    bool operator () (const node & a,const node & b) const
    {
       return b.dis<a.dis;
    }
};
bool vis[1000][1000];
priority_queue <node,vector<node>,cmp1> s;
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
int main(){
    int n,m;
    node start;
    node e1;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
        scanf(" %c",&map[i][j]);
        if(map[i][j]=='r'){
            start.x=i;
            start.y=j;
            start.dis=0;
        }
        if(map[i][j]=='a'){
            e1.x=i;
            e1.y=j;
        }
        }
    }
    s.push(start);
    int u=0;
    while(!s.empty()){
        node e;
        e=s.top();
        s.pop();
        if(e.x==e1.x&&e.y==e1.y){
        cout<<e.dis<<"\n";
        u=1;
        break;
        }
        node ne;
        ne=e;
        for(int i=0;i<4;i++)
        {
            ne.x=e.x+xx[i];
            ne.y=e.y+yy[i];
            if(ne.x<1||ne.y<1||ne.x>n||ne.y>m||map[ne.x][ne.y]=='#'||vis[ne.x][ne.y])continue;
            else{
            if(map[ne.x][ne.y]=='x'){
                ne.dis=e.dis+2;
            }
            else
            ne.dis=e.dis+1;
            vis[ne.x][ne.y]=true;
            s.push(ne);
            }
        }
    }
    if(!u)
    cout<<"Poor ANGEL has to stay in the prison all his life."<<"\n";
    while(!s.empty()){
        s.pop();
    }
    }

    return 0;
}