专栏首页WD学习记录牛客网 地牢逃脱

牛客网 地牢逃脱

题目:地牢逃脱

题目描述

给定一个 n 行 m 列的地牢,其中 '.' 表示可以通行的位置,'X' 表示不可通行的障碍,牛牛从 (x0 , y0 ) 位置出发,遍历这个地牢,和一般的游戏所不同的是,他每一步只能按照一些指定的步长遍历地牢,要求每一步都不可以超过地牢的边界,也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下,他需要多少步才可以离开这个地牢。

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m(1 <= n, m <= 50),表示地牢的长和宽。接下来的 n 行,每行 m 个字符,描述地牢,地牢将至少包含两个 '.'。接下来的一行,包含两个整数 x0, y0,表示牛牛的出发位置(0 <= x0 < n, 0 <= y0 < m,左上角的坐标为 (0, 0),出发位置一定是 '.')。之后的一行包含一个整数 k(0 < k <= 50)表示牛牛合法的步长数,接下来的 k 行,每行两个整数 dx, dy 表示每次可选择移动的行和列步长(-50 <= dx, dy <= 50)

输出描述:

输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢,如果永远无法离开,输出 -1。以下测试用例中,牛牛可以上下左右移动,在所有可通行的位置.上,地牢出口如果被设置在右下角,牛牛想离开需要移动的次数最多,为3次。

示例1

输入

3 3
...
...
...
0 1
4
1 0
0 1
-1 0
0 -1

输出

3

题目理解:

“地牢的出口可能在任意某个可以通行的位置上”

还有,“最坏情况下,他需要多少步才可以离开这个地牢”

——这两句话在一起,导致题意很不明确……

于是你只能看样例和解释揣测了……

最坏情况下,看上去不是他不知道出口在哪里然后随机乱走,因为样例解释里说了,最坏在右下角,要3步——完全不知道的情况下,怎么可能只走3步?完全可以先右边走了,再走到左边,这远大于3步。

OK,既然出口应该是知道的,而且走3步看上去是直接走的,那么问题的题意很大概率是这个:

现在知道牛牛自己的起点,在终点(出口)是所有可通行格子中的一个的情况下,设哪一个格子为终点,会导致牛牛要走出去的最小步数最大?

问题清楚多了……

从起点出发,BFS整个图,然后找距离最远的可通行点,作为答案,OVER。

解答:

参考了已经提交的解答

m,n=[int(i) for i in input().split()]# 获取行列  m n
maps=[input() for i in range(m)]# 获取地宫矩阵 ['...','...','...']
x,y=[int(num) for num in input().split()]# 获取初始点的位置
k=int(input())
move=[[int(x) for x in input().split()] for y in range(k)]
visit=[[True if maps[i][j]=='.' else False for j in range(n)] for i in range(m)]
N=sum(1 if visit[i][j] else 0 for i in range(m) for j in range(n))

def layer():
    if maps[x][y]=='x':
        return -1
    visit[x][y]=False
    step,count=1,1
    que=[[x,y]]
    while que:
        tmp=[]
        for i,j in que:
            for dx,dy in move:
                nx=i+dx
                ny=j+dy
                if 0<=nx<m and 0<=ny<n and maps[nx][ny]=='.' and visit[nx][ny]:
                    tmp.append([nx,ny])
                    count+=1
                    visit[nx][ny]=False
                if count==N:
                    return step
        que=tmp
        step+=1
    return -1
print(layer())

参考:地牢逃脱

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 吴恩达深度学习笔记 3.1~3.11 浅层神经网络

    神经网络的结构与逻辑回归类似,只是神经网络的层数比逻辑回归多了一层,多出的中间一层叫隐藏层,那么,神经网络的计算就相当于多进行一次逻辑回归的计算

    Dar_Alpha
  • 暗通道去雾算法原理及实现

    基本原理来源于何凯明大神的CVPR09的论文Single Image Haze Removal Using Dark Channel Prior

    和蔼的zhxing
  • 理论 | 朴素贝叶斯模型算法研究与实例分析

    朴素贝叶斯是一种构建分类器的简单方法。该分类器模型会给问题实例分配用特征值表示的类标签,类标签取自有限集合。所有朴素贝叶斯分类器都假定样本每个特征与其他特征都不...

    伏草惟存
  • 实现 | 朴素贝叶斯模型算法研究与实例分析

    构建一个快速过滤器来屏蔽在线社区留言板上的侮辱性言论。如果某条留言使用了负面或者侮辱性的语言,那么就将该留言标识为内容不当。对此问题建立两个类别: 侮辱类和非侮...

    伏草惟存
  • 排序算法

    ppjun
  • 一个随机播放的算法II

    音乐时光? 骑着车,戴着耳机,播放列表里有几首歌。 突然,很想听《且听风吟》,但是不想掏出手机,于是一路双击耳机播放键切歌。 emmm,下面是切过的歌:

    冰之角
  • 伪随机数生成算法

    伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。

    李拜六不开鑫
  • ZooKeeper典型应用场景一览(转)

    ZooKeeper是一个高可用的分布式数据管理与系统协调框架。基于对Paxos算法的实现,使该框架保证了分布式环境中数据的强一致性,也正是基于这样的特性,使得Z...

    会跳舞的机器人
  • 亚像素数值极值检测算法总结

    在计算机视觉领域,经常需要检测极值位置,比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等,有时只需要像素精度就可以,有时则需要...

    李拜六不开鑫
  • 深度 | 朴素贝叶斯模型算法研究与实例分析

    本节介绍朴素贝叶斯分类算法模型在中文领域中的应用。我们对新闻语料进行多文本分类操作,本文选择艺术、文学、教育、哲学、历史五个类别的训练文本,然后采用新的测试语料...

    伏草惟存

扫码关注云+社区

领取腾讯云代金券