NYOJ1100【WAJUEJI which home strong!】BFS+优先队列

2024-08-23 14:58

本文主要是介绍NYOJ1100【WAJUEJI which home strong!】BFS+优先队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

在一个山沟里,姐弟俩同时考上了大学。但由于家里拮据,所以这并不是什么好消息。父亲对孩子说:我就是砸锅卖铁也要把你们姐俩供出来。 当时的姐姐已经决定放弃上学的机会。 没想到第二天天还没亮,弟弟就偷偷带著几件破衣服和几个乾巴馒头走了,在姐姐枕边留下一个纸条: 姐,你别愁了,考上大学不容易,我出去打工供你。弟。 姐姐握著那张字条,趴在炕上,失声痛哭。 那一年,弟弟17岁,姐姐20岁。 姐姐用父亲满村子借的钱和弟弟在工地裏搬水泥挣的钱终於读到了大三。 一天姐姐正在寝室看书,同学跑进来对姐姐说,有个老乡在找你。姐姐很纳闷,走出去后,远远地看见弟弟,穿著满身是水泥和沙子的工作服。姐姐说,你怎和我同学说你是我老乡啊? 他笑著说,你看我穿的这样,说是你弟,你同学还不笑话你? 姐姐鼻子一酸,眼泪就落了下来。弟弟赶忙为姐姐擦掉眼泪,说:姐,你别哭,我这次来是想让你帮我打听一下,学挖掘机哪家强? 

 

在你的帮助下,弟弟踏上了去蓝翔的路。

那么问题就来了。

输入
第一个数T,T组测试数据。
两个数 n, m; ( 0< n , m <= 100 ) 表示一个h行m列的二维地图。
接下来n行每行m 个字符。
‘s’ 表示弟弟目前所在位置。
‘# ’表示此处为一座山。为了节省体力,不从此处通行。
从‘A’-‘Z’表示各地的经济水平,对应1-26,路过对应字符的地区需要交对应的生活费。
‘l’表示蓝翔技校的所在地。
s 与 l 均为小写字母。
弟弟只能走四个方向。
输出
输出一个数表示弟弟到达蓝翔需要的生活费最小是多少。
如果不能到达,输出 -1。
样例输入
3
3 5
#sVGF
A##ZA
lCDBC
3 3
sAB
ABS
ABl
3 3
s#B
###
ABl
样例输出
48
4
-1



#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int divs[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
int vis[105][105];
int mp[105][105];
int m,n,sx,sy,ex,ey;
struct node
{int x,y;int cnt;friend bool operator < (const node &a,const node &b){return a.cnt>b.cnt;}
};
int dfs()
{priority_queue<node>q;node now,tmp;now.x=sx;now.y=sy;now.cnt=0;vis[now.x][now.y]=1;q.push(now);while(!q.empty()){now=q.top();q.pop();if(now.x==ex&&now.y==ey)return now.cnt;for(int i=0; i<4; i++){tmp.x=now.x+divs[i][0];tmp.y=now.y+divs[i][1];tmp.cnt=now.cnt;if(tmp.x>=0&&tmp.y>=0&&tmp.x<n&&tmp.y<m&&!vis[tmp.x][tmp.y]&&mp[tmp.x][tmp.y]!='#'){if(mp[tmp.x][tmp.y]!='l')tmp.cnt=tmp.cnt+mp[tmp.x][tmp.y]-'A'+1;q.push(tmp);vis[tmp.x][tmp.y]=1;}}}return -1;
}
int main()
{int t;scanf("%d",&t);while(t--){memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for(int i=0; i<n; i++){getchar();for(int j=0; j<m; j++){scanf("%c",&mp[i][j]);if(mp[i][j]=='s')sx=i,sy=j;if(mp[i][j]=='l')ex=i,ey=j;}}int res=dfs();printf("%d\n",res);}
}




这篇关于NYOJ1100【WAJUEJI which home strong!】BFS+优先队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099709

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

log4j2相关配置说明以及${sys:catalina.home}应用

${sys:catalina.home} 等价于 System.getProperty("catalina.home") 就是Tomcat的根目录:  C:\apache-tomcat-7.0.77 <PatternLayout pattern="%d{yyyy-MM-dd HH:mm:ss} [%t] %-5p %c{1}:%L - %msg%n" /> 2017-08-10