文档章节

优先队列广搜 hdu 1242

洛伊佩拉
 洛伊佩拉
发布于 2013/11/15 21:27
字数 557
阅读 23
收藏 0
Rescue
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.
 

Output
For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."
Sample Input
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
 

Sample Output
13
 

http://acm.hdu.edu.cn/showproblem.php?pid=1242

code:

#include <iostream>
#include "stdio.h"
#include "queue.h"
#include "memory.h"

char map[205][205];            //图的定义 
char vit[205][205];            //图访问的判断 


int fangxiang[4][2]={1,0,-1,0,0,1,0,-1};
using namespace std;

struct point
{
    int x;
    int y;
    int step;
    friend bool operator<(point n1,point n2)  
    {  
        return n2.step<n1.step;  
    }  
};
int n,m;            //图的长宽 
point end;

priority_queue <point> q;  //定义一个优先队列  
void bfs(void)
{
    
    point cut;
    while(!q.empty())        //队列不为空 
    {
        cut=q.top();
         q.pop();
        vit[cut.x][cut.y]=1;    //该位置访问过
        
        if(cut.x==end.x&&cut.y==end.y)
        {
            end.step=cut.step;
            return;
        }
        
        int newx,newy;        //新坐标
         int i;
         for(i=0;i<4;i++)
         {
             newx=cut.x+fangxiang[i][0];
             newy=cut.y+fangxiang[i][1];
             if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&!vit[newx][newy]&&(map[newx][newy]=='.'||map[newx][newy]=='x'||map[newx][newy]=='a'))        //满足条件    
             {
                 point feature;        //可行点 
                 feature.x=newx;
                 feature.y=newy;
                 vit[newx][newy]=1;
                 if(map[newx][newy]=='x')            //有警卫 
                 {
                     feature.step=cut.step+2;
                 }else
                 {
                     feature.step=cut.step+1;
                 }
             //    printf("x=%d,y=%d,step=%d\n",newx,newy,feature.step);
                 q.push(feature);
                 
             }
             
         }
        
    }
}

int main(int argc, char *argv[])
{

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        
        int i,j;
        point start;
        while(!q.empty())        //队列清空 
        {
            q.pop();
        }
        memset(vit,0,sizeof(vit));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='r')    //找到起点 
                {
                    start.x=i;
                    start.y=j;
                    start.step=0;
                }
                if(map[i][j]=='a')    //找到终点 
                {
                    end.x=i;
                    end.y=j;
                    end.step=-1;
                }
            }
        }
        
        q.push(start);
        bfs();            //开始广度搜索 
        
        if(end.step!=-1)
        {
            printf("%d\n",end.step);
        }else
        {
            printf("Poor ANGEL has to stay in the prison all his life.\n");
        }
        
    } 
    return 0;
}

 

 

 

© 著作权归作者所有

洛伊佩拉

洛伊佩拉

粉丝 4
博文 73
码字总数 27576
作品 0
绍兴
私信 提问
深搜和广搜--原理彼此的优缺点

转自http://www.cnblogs.com/A-FM/p/5240887.html 一般来说,广搜常用于找单一的最短路线,或者是规模小的路径搜索,它的特点是"搜到就是最优解", 而深搜用于找多个解或者是"步数已知(好比...

Dear_Jia
2017/11/16
0
0
图的理解:深度优先和广度优先遍历

遍历 ------------------------------图的遍历,所谓遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略: 深度优先遍历 广度优先遍历 深度...

datacube
2016/06/18
39
0
【算法系列 三】 Quene

拓扑排序问题(HDU 1285) import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer; public class Main{static int[] i......

Hosee
2016/03/01
102
0
深度优先遍历 (DFS) 与广度优先遍历 (BFS)

前端小兵,不吝赐教 背景 看了很多前辈的分享后,笔者今天想整理下所理解的图的遍历算法。 图的遍历算法分为深度优先遍历与广度优先遍历,这两种算法从字面上了解的话,可以很清楚的知道。 ...

Wenson_Jay
07/22
0
0
HDU 3085 Nightmare Ⅱ

Nightmare Ⅱ   Last night, little erriyue had a horrible nightmare. He dreamed that he and his girl friend were trapped in a big maze separately. More terribly, there are two......

suvvm
2018/12/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

64.监控平台介绍 安装zabbix 忘记admin密码

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍: 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111
今天
13
0
当餐饮遇上大数据,嗯真香!

之前去开了一场会,主题是「餐饮领袖新零售峰会」。认真听完了餐饮前辈和新秀们的分享,觉得获益匪浅,把脑子里的核心纪要整理了一下,今天和大家做一个简单的分享,欢迎感兴趣的小伙伴一起交...

数澜科技
今天
7
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

本文作者:PETER LAI ,是 Diode 的区块链工程师。在进入软件开发领域之前,他主要是在做工商管理相关工作。Peter Lai 也是一位活跃的开源贡献者。目前,他正在与 Diode 团队一起开发基于区块...

红薯
今天
10
0
CC攻击带来的危害我们该如何防御?

随着网络的发展带给我们很多的便利,但是同时也带给我们一些网站安全问题,网络攻击就是常见的网站安全问题。其中作为站长最常见的就是CC攻击,CC攻击是网络攻击方式的一种,是一种比较常见的...

云漫网络Ruan
今天
12
0
实验分析性专业硕士提纲撰写要点

为什么您需要研究论文的提纲? 首先当您进行研究时,您需要聚集许多信息和想法,研究论文提纲可以较好地组织你的想法, 了解您研究资料的流畅度和程度。确保你写作时不会错过任何重要资料以此...

论文辅导员
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部