首页 > 其他分享 >hdu:Rescue(bfs+优先队列)

hdu:Rescue(bfs+优先队列)

时间:2023-08-27 20:45:12浏览次数:41  
标签:hdu ch Rescue Angel int st bfs vis

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+优先队列

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=210;
char ch[N][N];
bool vis[N][N];
int st[N][N],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{
	int x,y,s;
	bool operator < (const node &T1) const
	{
		return s>T1.s;
	}
};

int n,m;

void bfs(int x,int y)
{
	memset(vis,0,sizeof vis);
	priority_queue<node> q;
	q.push({x,y,0});
	vis[x][y]=1;
	while(q.size())
	{
		auto p=q.top();
		q.pop();
		int a=p.x,b=p.y,s=p.s;
		if(st[a][b]==-1)
		{
			cout<<s<<'\n';return ;
		}
		for(int i=0;i<4;++i)
		{
			int xx=a+dir[i][0];
			int yy=b+dir[i][1];
			if(xx>=0&&xx<n&&yy>=0&&yy<m&&st[xx][yy]&&!vis[xx][yy])
			{
				vis[xx][yy]=1;
				q.push({xx,yy,s+st[a][b]});
			}
		}
	}
	cout<<"Poor ANGEL has to stay in the prison all his life.\n";
}

int main()
{
    while(cin>>n>>m)
    {
    	int x,y;
    	for(int i=0;i<n;++i)
    	 for(int j=0;j<m;++j)
    	 {
    	  cin>>ch[i][j];
    	  if(ch[i][j]=='.') st[i][j]=1;
    	  else if(ch[i][j]=='#') st[i][j]=0;
    	  else if(ch[i][j]=='x') st[i][j]=2;
    	  else if(ch[i][j]=='a') st[i][j]=1,x=i,y=j;
    	  else st[i][j]=-1;
    	 }
    	bfs(x,y);
    	
    }
    return 0;
}

标签:hdu,ch,Rescue,Angel,int,st,bfs,vis
From: https://www.cnblogs.com/ruoye123456/p/17660777.html

相关文章

  • hdu:Knight Moves(bfs)
    ProblemDescriptionAfriendofyouisdoingresearchontheTravelingKnightProblem(TKP)whereyouaretofindtheshortestclosedtourofknightmovesthatvisitseachsquareofagivensetofnsquaresonachessboardexactlyonce.Hethinksthatthe......
  • hdu:A strange lift(bfs)
    ProblemDescriptionThereisastrangelift.Theliftcanstopcanateveryfloorasyouwant,andthereisanumberKi(0<=Ki<=N)oneveryfloor.Thelifthavejusttwobuttons:upanddown.Whenyouatfloori,ifyoupressthebutton“UP”,youwi......
  • leetcode 题库994——bfs典型解法(队列+递归实现)
     classSolution:deforangesRotting(self,grid:list[list[int]])->int:m,n=len(grid),len(grid[0])queue,good=[],[]defbfs(queue,good,m,n,grid):times=0directions=[(-1,0),(1,0),(0,1),(0,-1)]......
  • hdu:一个人的旅行
    ProblemDescription虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中会遇见很多人(白马王子,0),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽......
  • hdu:悼念512汶川大地震遇难同胞——珍惜现在,感恩生活
    ProblemDescription急!灾区的食物依然短缺!为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。请问:你用有限的资金最多能采购多少公斤粮食呢?后记:人生是一个充满了......
  • hdu:Piggy-Bank(背包)
    ProblemDescriptionBeforeACMcandoanything,abudgetmustbepreparedandthenecessaryfinancialsupportobtained.ThemainincomeforthisactioncomesfromIrreversiblyBoundMoney(IBM).Theideabehindissimple.WheneversomeACMmemberhasany......
  • hdu:免费馅饼
    ProblemDescription都说天上不会掉馅饼,但有一天gameboy正走在回家的小径上,忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了,这馅饼别处都不掉,就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了,所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能......
  • hdu:搬寝室
    ProblemDescription搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2k件过去就行了.但还是会很累,因为2k也不小是一个不大......
  • hdu:不容易系列之(3)—— LELE的RPG难题
    ProblemDescription人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即”可乐”),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题:有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要......
  • hdu:畅通工程(并查集)
    ProblemDescription某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?Input测试输入包含若干......