2727:仙岛求药

2727:仙岛求药

总时间限制:1000ms内存限制:65536kB描述少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.

输入输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始,两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:

1) ‘@’:少年李逍遥所在的位置;

2) ‘.’:可以安全通行的方格;

3) ‘#’:有怪物的方格;

4) ‘*’:仙药所在位置。

当在一行中读入的是两个零时,表示输入结束。输出对于每组测试数据,分别输出一行,该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。样例输入

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#.@.## 
.#..#. 
0 0

样例输出

10
8
-1

bfs裸题,注意每组数据之间的衔接
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 int bgx,bgy,edx,edy;
 7 const int MAXN=1001;
 8 int map[MAXN][MAXN];
 9 bool vis[MAXN][MAXN];
10 int xx[6]={-1,+1,0,0};
11 int yy[6]={0,0,-1,+1};
12 int n,m;
13 struct node
14 {
15     int x;
16     int y;
17     int step;
18 }cur,nxt;
19 queue<node>q;
20 void bfs(int x,int y)
21 {
22     while(q.size()!=0)q.pop();
23     cur.x=x;    cur.y=y;    cur.step=0;
24     q.push(cur);
25     vis[x][y]=1;
26     int flag=0;
27     while(q.size()!=0)
28     {
29         node p=q.front();
30         q.pop();
31         for(int i=0;i<4;i++)
32         {
33             int wx=p.x+xx[i];
34             int wy=p.y+yy[i];
35             if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&vis[wx][wy]==0&&map[wx][wy]!=1)
36             {
37                 if(map[wx][wy]==2)
38                 {
39                     printf("%d\n",p.step+1);
40                     flag=1;
41                     break;
42                 }
43                 else
44                 {
45                     nxt.x=wx;
46                     nxt.y=wy;
47                     nxt.step=p.step+1;
48                     q.push(nxt);
49                     vis[wx][wy]=1;
50                 }
51             }
52         }
53         if(flag==1)break;
54     }
55     if(flag==0)
56     printf("-1\n");
57 }
58 int main()
59 {
60     while(scanf("%d%d",&n,&m))
61     {
62         memset(map,0,sizeof(map));
63         memset(vis,0,sizeof(vis));
64         if(n==0&&m==0)break;
65         for(int i=1;i<=n;i++)
66         {
67             for(int j=1;j<=m;j++)
68             {
69                 char c;
70                 cin>>c;
71                 if(c=='@')     {bgx=i;bgy=j;map[i][j]=1;}
72                 if(c=='*')    {edx=i;edy=j;map[i][j]=2;}
73                 if(c=='#')     {map[i][j]=1;}
74                 if(c=='.')     {map[i][j]=0;}
75             }
76         }
77         bfs(bgx,bgy);
78     }
79     return 0;
80 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端说吧

JS-缓冲运动基础结构

课程来源路径:智能社得开发课程:https://ke.qq.com/webcourse/index.html#course_id=152997&term_id=...

9310
来自专栏生信技能树

二代测序数据拼接之原理篇

前前后后接触了一些基因组和转录组拼接的工作,而且后期还会持续进行。期间遇到了各种各样莫名其妙的坑,也尝试了一些不同的方法和软件,简单做一个阶段性小结,本篇是原理...

1.7K50
来自专栏计算机视觉与深度学习基础

HDU4832

由于水平和竖直相互独立,所以可以分开计数,最后再用组合数算一下,万年老坑long long #include<cstdio> #include<iostream...

214100
来自专栏小樱的经验随笔

基于连通性状态压缩的动态规划问题

基于连通性状态压缩的动态规划问题 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题.在状态压缩的基础上,有一类问题的状态中...

36580
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列七:基于SSE实现的极速的矩形核腐蚀和膨胀(最大值和最小值)算法。

  因未测试其他作者的算法时间和效率,本文不敢自称是最快的,但是速度也可以肯定说是相当快的,在一台I5机器上占用单核的资源处理 3000 * 2000的灰度...

44190
来自专栏ascii0x03的安全笔记

使用sklearn构建含有标量属性的决策树

网络上使用sklearn生成决策树的资料很多,这里主要说明遇见标量数据的处理。 经查验参考资料,sklearn并非使用了课上以及书上讲的ID3算法,而是选择了C...

42760
来自专栏数说工作室

【SAS Says】基础篇:基本统计、相关分析与回归分析

特别说明:本节【SAS Says】基础篇:SAS宏初步,用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择 S...

48950
来自专栏云时之间

NLP系列学习:常用的语言平滑模型

语言模型常见的平滑算法就那几种,一般的教程都不提分几种的模式、分类。 不过在MIT的NLP课程ppt中总结说有三种模式:Discounting, Interp...

33560
来自专栏温安适的blog

以回溯解高速公路重建与正序全排列

39660
来自专栏null的专栏

数据结构和算法——动态规划

一、动态规划的思想     动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行...

34540

扫码关注云+社区

领取腾讯云代金券