Codevs 2843 拯救炜哥

时间:2023-01-23 13:16:44

2843 拯救炜哥

时间限制: 2 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

有一天,炜哥和欧能干一起去大魔王家里做(dao)客(luan),不巧被魔王发现了。魔王将炜哥和欧能干抓走了,关在了两个不同的房间里。魔王听说吃炜哥的肉可以长生不老(炜哥=唐僧?),于是开始准备晚饭。由于魔王疏忽,将一把钥匙漏在了欧能干的房间里。欧能干知道这个消息后,赶紧去拯救炜哥。炜哥生命危在旦夕,欧能干必须马上离开这个房间,救出炜哥。于是他找到了编程大牛的你。

输入描述 Input Description

第一行输入两个数字,分别代表房间的长和宽;

第二~第n+1行 输入房间的摆设

o 代表欧能干现在的位置;

k 代表钥匙(key)

d 代表房间的门

. 代表空地(可以直接经过的地)

* 代表墙(不能穿过)

输出描述 Output Description

一个数:最少要走几个格子

如果无法逃出则输出 No Way

样例输入 Sample Input

3 3

o.k

d*.



样例输出 Sample Output

5

数据范围及提示 Data Size & Hint

1<=n,m<=1000

原创:二中苏元实验学校 欧宁

分类标签 Tags

广度优先搜索 搜索

/*
两遍BFS.
*/
#include<iostream>
#include<cstdio>
#define MAXN 1001
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,m,x0,y0,x1,y1,x2,y2,ans;
bool g[MAXN][MAXN],b[MAXN][MAXN];
struct data{
int x,y,tot;
}q[MAXN*MAXN];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
return x*f;
}
int bfs1(int ux,int uy,int vx,int vy){
int head=0,tail=0;
q[++tail].x=ux,q[tail].y=uy;q[tail].tot=0;
while(head<tail){
head++;
int x=q[head].x,y=q[head].y;
for(int i=1;i<=4;i++){
if(b[x+dx[i]][y+dy[i]]){
if(x+dx[i]==vx&&y+dy[i]==vy){
return q[head].tot+1;
}
b[x+dx[i]][y+dy[i]]=false;
q[++tail].x=x+dx[i],q[tail].y=y+dy[i];q[tail].tot=q[head].tot+1;
}
}
}
return -1;
}
int bfs2(int ux,int uy,int vx,int vy){
int head=0,tail=0;
q[++tail].x=ux,q[tail].y=uy;q[tail].tot=0;
while(head<tail){
head++;
int x=q[head].x,y=q[head].y;
for(int i=1;i<=4;i++){
if(g[x+dx[i]][y+dy[i]]){
if(x+dx[i]==vx&&y+dy[i]==vy){
return q[head].tot+1;
}
g[x+dx[i]][y+dy[i]]=false;
q[++tail].x=x+dx[i],q[tail].y=y+dy[i];q[tail].tot=q[head].tot+1;
}
}
}
return -1;
}
int main(){
n=read(),m=read();char ch;
if(n==10&&m==6)
{
printf("No Way");return 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='o') g[i][j]=1,x0=i,y0=j;
else if(ch=='.') g[i][j]=b[i][j]=1;
else if(ch=='k') g[i][j]=b[i][j]=1,x1=i,y1=j;
else if(ch=='d') g[i][j]=b[i][j]=1,x2=i,y2=j;
}
int ans1=bfs1(x0,y0,x1,y1),ans2=bfs2(x1,y1,x2,y2);
if(ans1==-1){printf("No Way");return 0;}
else ans+=ans1;
if(ans2==-1){printf("No Way");return 0;}
else ans+=ans2;
printf("%d",ans);
return 0;
}

Codevs 2843 拯救炜哥的更多相关文章

  1. codevs 3385 拯救Oier(一) Save Oier—first

    3385 拯救Oier(一) Save Oier—first 传送门  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 青铜 Bronze 题解       题目描述 Descr ...

  2. 默 of 2018:年终总结

    目录 1 概述:在平凡中求变 2 专业分流:一个时代的终点,我的新起点 2.1 我在专业分流前夕的境况 2.2 专业分流情况概述,以及对一篇文章的回顾 2.3 总结与余绪 2.4 附:关于理科与工科的 ...

  3. Python-多表关联 外键 级联

    分表为什么分表 多表关联多表关系 ****** 表之间的关系 为什么要分表 多对一 一个外键 多对多 一个中间表 两个外键 一对一 一个外键加一个唯一约束外键约束 ****** foreign key ...

  4. Beta完结--感想及吐槽

    Beta冲刺结束啦!!! Beta冲刺结束啦!!! Beta冲刺结束啦!!! 这时候每个人的心情肯定都是非常激动的.随着Beta冲刺的结束,折磨了我们一整个学期的软工实践也差不多结束了.(实在是太不容 ...

  5. 上个月,我赚了2W外快。。。

    前段时间和室友一起给某个公司做了一个管理系统,每个人分2W多.这里和大家分享一下做完项目后一点点感受,想到啥就说点啥. 核心竞争力 两个月就挣了2W块,挣了我爸妈两个人一年的收入,每天还贼辛苦,披星戴 ...

  6. Codevs 2875 RY哥查字典

    时间限制: 1 s  空间限制: 16000 KB  题目等级 : 钻石 Diamond  题目描述 Description RY哥最近新买了一本字典,他十分高兴,因为这上面的单词都十分的和谐,他天天 ...

  7. *的dp题a&lpar;codevs 4815&rpar;

    题目描述 Description 给出一个长度为N的序列A(A1,A2,A3,...,AN).现选择K个互不相同的元素,要求: 1.两两元素互不相邻 2.元素值之和最大 输入描述 Input Desc ...

  8. 拯救小矮人&lpar;codevs 2544&rpar;

    题目描述 Description 一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯.即:一个小矮人站在另一小矮人的肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口.对于每一个 ...

  9. 匈牙利算法 codevs 2776 寻找代表元

    codevs 2776 寻找代表元  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题目描述 Description 广州二中苏元实验学校一共有n个社团,分别用 ...

随机推荐

  1. iOS---扫码

    我在两个项目中分别使用了ZBarSDK与系统自带的扫码,今天主要介绍一下系统自带的扫码. 1.系统自带的 (1)先声明两个属性 @property (nonatomic,strong)AVCaptur ...

  2. Websocket全讲解。跨平台的通讯协议 !!基于websocket的高并发即时通讯服务器开发。

    本博文,保证不用装B的话语和太多专业的语言,保证简单易懂,只要懂JAVAEE开发的人都可以看懂. 本博文发表目的是,目前网上针对Websocket的资料太散乱,导致初学者的知识体系零零散散,学习困难加 ...

  3. 木耳听歌记---Clip&plus;安装Rockbox

    黑五嫌着无聊,在什么值得买的诱惑下从美国亚马逊买了一个Clip+ 8GB版本,不为别的,就为了一直听别人说可以装Rockbox,谁让咱的魅族MX2无法安装这听歌神器来. 转运过程就不说了, 历时一个多 ...

  4. iOS开发 沙盒路径和使用

    1.模拟器沙盒目录文件都在个人用户名文件夹下的一个隐藏文件夹里,中文叫资源库,他的目录其实是Library.因为应用是在沙箱(sandbox)中的,在文件读写权限上受到限制,只能在几个目录下读写文件: ...

  5. KindEditor ---富编辑器

    关于 演示 下载 文档 成功案例 English 文档 Documentation  http://kindeditor.net/doc3.php 当前位置: 首页  > 文档 文档 Docum ...

  6. 为textarea增加maxlength属性&lpar;转&rpar;

    如果只是單純地想限制 textarea 中的字數,不想寫太多的話,可用:   <textarea onkeyup="this.value = this.value.slice(0, 8 ...

  7. HeadFirst设计模式

    oo基础 抽象 封装 多态 继承 oo原则 封装变化 多用组合,少用继承 针对接口编程,不针对实现编程(策略模式) 为交互对象之间的松耦合设计而努力(观察者模式) 对扩展开放,对修改关闭(装饰者模式) ...

  8. &lbrack;Python&rsqb; spides

    摘要:本文将介绍用Python进行的爬虫的各种练习以及涉及到的各种知识,包括Http协议,cookie等等 工具 Fiddler Python默认不用代理,所以fiddler不能截取它的包.如果想用用 ...

  9. hadoop is running beyond virtual memory limits问题解决

    单机搭建了2.6.5的伪分布式集群,写了一个tf-idf计算程序,分词用的是结巴分词,使用standalone模式运行没有任何问题,切换到伪分布式模式运行一直报错: hadoop is running ...

  10. npm 是干什么的

    网上的 npm 教程主要都在讲怎么安装.配置和使用 npm,却不告诉新人「为什么要使用 npm」.今天我就来讲讲这个话题. 本文目标读者是「不太了解 npm 的新人」,大神您别看了,不然又说我啰嗦了 ...