nyoj--1100--WAJUEJI which home strong!(bfs)
2024-08-27 20:01:37
WAJUEJI which home strong!
时间限制:1000 ms | 内存限制:65535 KB
难度:2
- 描述
-
在一个山沟里,姐弟俩同时考上了大学。但由于家里拮据,所以这并不是什么好消息。父亲对孩子说:我就是砸锅卖铁也要把你们姐俩供出来。 当时的姐姐已经决定放弃上学的机会。 没想到第二天天还没亮,弟弟就偷偷带著几件破衣服和几个乾巴馒头走了,在姐姐枕边留下一个纸条: 姐,你别愁了,考上大学不容易,我出去打工供你。弟。 姐姐握著那张字条,趴在炕上,失声痛哭。 那一年,弟弟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 -
-
刚开始字符没有判断,总是多加一个‘l’的值,,,,,真是醉了
-
-
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct node
{
int x,y;
int step;
friend bool operator < (node s1,node s2)
{
return s1.step>s2.step;
}
}p,temp;
char map[110][110];
int ans,x,y,n,m,vis[110][110];
bool flag;
bool judge(node s)
{
if(s.x<0||s.x>=n||s.y<0||s.y>=m)
return true;
if(vis[s.x][s.y]||map[s.x][s.y]=='#')
return true;
return false;
}
void bfs()
{
priority_queue<node>q;
memset(vis,0,sizeof(vis));
p.x=x;p.y=y;p.step=0;
vis[x][y]=1;
q.push(p);
while(!q.empty())
{
p=q.top();
q.pop();
if(map[p.x][p.y]=='l')
{
ans=min(p.step,ans);
flag=false;
// return ;
continue;
}
for(int i=0;i<4;i++)
{
temp.x=p.x+dx[i];
temp.y=p.y+dy[i];
int s=0;
if(judge(temp)) continue;
if(map[temp.x][temp.y]>='A'&&map[temp.x][temp.y]<='Z')
s=map[temp.x][temp.y]-65+1;
temp.step=p.step+s;
vis[temp.x][temp.y]=1;
q.push(temp);
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
for(int j=0;j<m;j++)
{
if(map[i][j]=='s')
{
x=i;y=j;
}
}
}
ans=0x3f3f3f;
flag=true;
bfs();
if(!flag)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}
最新文章
- PHP中的闭包和匿名函数
- XAMPP 在windows下无法启动Apache解决方案
- Cisco IOS Basic CLI Configuration : Switch Port Command
- ZOJ-2365 Strong Defence 贪心,BFS
- Android: ScrollView监听滑动到顶端和底端
- js关闭当前页面/关闭当前窗口/移动端 代码
- 浅谈Jquery的使用下篇
- Android如何调用第三方SO库(转)
- day002-HTML知识点总结:浏览器兼容性之指定IE浏览器使用chrome内核渲染页面
- Web缓存和静态化
- ubuntu安装git
- 小程序授权demo
- charles抓包的安装,使用说明以及常见问题解决(windows)
- 每月IT摘录201901
- 深入理解JavaScript函数参数
- 为树莓派添加一个强实时性前端[原创cnblogs.com/helesheng]
- spring3-spring的事务管理机制
- Problem D: 零起点学算法94——输出矩阵
- mysql 8 安装及更改密码
- HTML初识(Day46)