rescue（BFS+优先队列）.#####..a#..r...#x……##..

59 阅读 0 评论 39 点赞

我是靠谱客的博主安静野狼，最近开发中收集的这篇文章主要介绍rescue（BFS+优先队列）.#####..a#..r...#x……##..，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description
Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs,
and GUARDs in the prison.

Angel’s friends want to save Angel. Their task is: approach Angel. We assume that “approach Angel” is to get to the position where Angel stays. When there’s a
guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes
1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input
First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. “.” stands for road, “a” stands for Angel, and “r” stands for each of Angel’s friend.

Process to the end of the file.

Sample Input
7 8

.#####.

.a#..r.

..#x…

..#..#.#

…##..

.#……
……..
Sample Output
13

题意：r为起点，a为终点，x是守卫，”.”是道路，遇到道路，消耗1个单位时间，遇到守卫，消耗2个单位时间，给定一个矩阵，问r能否到a，能到，求最少时间；不能，输出”Poor ANGEL has to stay in the prison all his life.” （不含引号）

思路：优先队列和BFS 从小到大排序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,xx,yy,flag;
int vis[205][205];///标记点是否走过
char a[205][205];///输入的矩阵数组
int dxy[4][2]= {1,0,-1,0,0,1,0,-1};///方向数组
struct node
{
    int x,y;///点的坐标（x,y）
    int cnt;///从起点该点所用的步数
    friend bool operator <(const node a,const node b)///cnt从小到大排序
    {
        return a.cnt>b.cnt;
    }
};
void bfs()
{
    node now,next;
    now.x=xx;
    now.y=yy;
    now.cnt=0;
    priority_queue<node> qq;
    qq.push(now);
    vis[xx][yy]=1;
    while(!qq.empty())
    {
        now=qq.top();///取队头
        qq.pop();///删除队头
        for(int i=0; i<4; i++)
        {
            next=now;
            next.x+=dxy[i][0];
            next.y+=dxy[i][1];
            int x=next.x,y=next.y;
            if(a[x][y]=='a') ///到达终点a
            {
                flag=1;///置1表示可以救出
                printf("%dn",now.cnt+1);///直接输出比较好，返回再判断可能会出错！！！
                return ;
            }
            if((a[x][y]=='.'||a[x][y]=='x')&&x>=0&&y>=0&&x<n&&y<m&&!vis[x][y])
            {
                vis[x][y]=1;
                if(a[x][y]=='.') ///如果该点是道路
                    next.cnt++;
                else ///如果该点是守卫
                    next.cnt+=2;
                qq.push(next);
            }
        }
    }
}
int main()
{
    //freopen("E:/in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i<n; i++)
            scanf("%s",&a[i]);
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(a[i][j]=='r') ///r为起点
                {
                    xx=i;
                    yy=j;
                }
        flag=0; ///是否能够救出的标志
        memset(vis,0,sizeof(vis));
        bfs();
        if(!flag)  ///如果不能救出
            printf("Poor ANGEL has to stay in the prison all his life.n");
    }
    return 0;
}