zoj 1649

63 阅读 0 评论 42 点赞

我是靠谱客的博主秀丽小笼包，最近开发中收集的这篇文章主要介绍zoj 1649，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这题纠结了一阵。。

/*
zoj_1649    搜索
毫无疑问是bfs啦。。本题x的出现是难点。
每次过x的时候step是要+2，但是+2以后它应该放到队列的哪个位置呢？
我一开始的想法是先用一个临时队列存起来，在下一轮的时候让临时队列里的东西进主队列。。然后一直wa。。
最后才明白，每一轮只消耗一个元素，在下一轮放进去显然不一定是它该进主队列的时候。。当然改进的话是
用临时队列存，在下一轮开始每次都判断临时队列里的元素该不该进主队列。。。这样好像可行。。不过很烦。。

最后实在烦了。。用优先队列让它自己慢慢排序去。。
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <queue>
#include <iomanip>
using namespace std;
string map[210];
int flag[210][210]; //这个flag当然可以开bool的，不过为了方便检查我改成了int，记录路径
struct node
{
    int x;
    int y;
    int step;
};
int way[4][2]={0,1,0,-1,1,0,-1,0};

bool operator<(const node &a,const node &b)
{
     if(a.step>b.step) return true;
     else return false;
}

int main()
{
    int i,j,n,m,cur;
    node t,tt;
    bool fail;
    priority_queue <node>q;
    while( cin>>n>>m )
    {
        memset( flag,0,sizeof(flag) );
        for( i=0;i<n;i++ )
            cin>>map[i];
        for( i=0;i<n;i++ )
        {
            for( j=0;j<m;j++ )
            {
                if( map[i][j]=='r' )
                {
                    t.x=i;
                    t.y=j;
                    t.step=1;
                    flag[t.x][t.y]=1;
                    q.push(t);
                }
            }
        }
        fail=true;
        cur=1;
        while( !q.empty() )
        {
            t=q.top();
            q.pop();
            if( map[t.x][t.y]=='a' )
            {
                fail=false;
                cout<<t.step-1<<endl;
                break;
            }
            for( i=0;i<4;i++ )
            {
                tt.x=t.x+way[i][0];
                tt.y=t.y+way[i][1];
                if( tt.x>=0 && tt.x<n && tt.y>=0 && tt.y<m && !flag[tt.x][tt.y] )
                {
                    if( map[tt.x][tt.y]=='.' ||  map[tt.x][tt.y]=='a' )
                    {
                       // cout<<tt.x<<" "<<tt.y<<" "<<t.step+1<<endl;
                        tt.step=t.step+1;
                        flag[tt.x][tt.y]=tt.step;
                        q.push( tt );
                    }
                    else if( map[tt.x][tt.y]=='x' )
                    {
                        tt.step=t.step+2;
                        flag[tt.x][tt.y]=tt.step;
                        q.push( tt );
                    }
                }
            }
           // cout<<endl;
        }
        if( fail )  cout<<"Poor ANGEL has to stay in the prison all his life.n";
   /*     for( i=0;i<n;i++ )
        {
            for( j=0;j<m;j++ )
            {
                cout<<setw(4)<<flag[i][j];
            }
            cout<<endl;
        }*/
        while( !q.empty() ) q.pop();
    }
    return 0;
}