HDU 1242 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
分析:
bfs即可,可能有多个’r’(天使的朋友),而’a’(天使)只有一个,从’a’开始搜,找到的第一个’r’即为所求
需要注意的是这题宽搜时存在障碍物,遇到’x’点是,时间+2,如果用普通的队列就并不能保证每次出队的是时间最小的元素,所以要用优先队列。
代码:
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int n,m,sx,sy;
int flg[4][2]= {{-1,0},{1,0},{0,1},{0,-1} };
char Map[209][209];
int vis[209][209];
struct Node
{
int x,y;
int step;
friend bool operator<(const Node &a,const Node &b)
{
return a.step>b.step;
}
};
int bfs(int x,int y)
{
Node Now,Next;
Now.x=x;
Now.y=y;
Now.step=0;
priority_queue<Node> q;
q.push(Now);
while(!q.empty())
{
Now=q.top();
q.pop();
//printf("%d %d\n",Now.x,Now.y);
if(Map[Now.x][Now.y]=='r')
{
// printf("@@@@@@@\n");
return Now.step;
}
for(int i=0; i<4; i++)
{
Next.x=Now.x+flg[i][0];
Next.y=Now.y+flg[i][1];
if(Next.x>=0&&Next.x<n&&Next.y>=0&&Next.y<m&&Map[Next.x][Next.y]!='#'&&vis[Next.x][Next.y]==0)
{
vis[Next.x][Next.y]=1;
if(Map[Next.x][Next.y]=='x')
Next.step=Now.step+2;
else
Next.step=Now.step+1;
q.push(Next);
}
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(vis,0,sizeof(vis));
for(int i=0; i<n; i++)
scanf(" %s",Map[i]);
int flag=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(Map[i][j]=='a')
{
sx=i;
sy=j;
flag=1;
// printf("%d %d\n",sx,sy);
break;
}
}
if(flag==1)
break;
}
vis[sx][sy]=1;
int ans=bfs(sx,sy);
if(ans==-1)
printf("Poor ANGEL has to stay in the prison all his life.\n");
else
printf("%d\n",ans);
}
}
最新文章
- 【实战Java高并发程序设计6】挑战无锁算法:无锁的Vector实现
- 《Entity Framework 6 Recipes》中文翻译系列 (36) ------ 第六章 继承与建模高级应用之TPC继承映射
- U-Mail反垃圾邮件网关过滤Locky勒索邮件
- 将表里的数据批量生成INSERT语句的存储过程 继续增强版
- sql server 日期相关操作
- U盘操作系统,Kali Linux操作系统安装
- WPF:在ControlTemplate中使用TemplateBinding
- nginx+tomcat集群配置(4)--rewrite规则和多应用根目录设定思路
- java中getBytes方法可能使图片文件产生的问题
- DropzoneJS 使用指南
- servlet中Java连接数据库后的基本操作
- Internet Explorer已限制此网页运行可以访问计算机的脚本或ActiveX控件
- User_Agent_List 浏览器信息列表
- 利用Hessian如何实现Webservice
- c#汉字转为拼音
- POJ3468--A Simple Problem with Integers(Splay Tree)
- AngularJS心得体会
- html5 中的SVG 和canvas
- mysql时间戳的获取
- Java中增强for循环的用法