#S1D12. Day12_救赎之道
Day12_救赎之道
题目背景
众所不周知,高中时 PC 长期沉迷于编写 Minecraft 服务器小游戏插件。其中,他对 “动态迷宫” 情有独钟。基本的原理是,在每次游戏开始时按给定大小,随机生成一座新的迷宫给玩家,而不是重复使用同一座。这样可以保证玩家每次游玩时要走的路线都不一样。
但由于当时的 PC 太笨了,随机生成的迷宫有概率会出现 入口 到 出口 之间 没有通路 的情况。显然这对玩家很不友好,所以当出现这种情况时 PC 会选择重新生成迷宫,直到 存在通路 为止。那么,怎么才能确定 入口 到 出口 间有没有通路呢?这个问题曾经困扰了 PC 许久,彼时形如 ChatGPT 的大语言模型还未像现如今这样家喻户晓。最终,PC 通过翻找各种技术帖和博客,找出了解决这个问题的办法。那么,如果你是 PC,你能想办法在一座迷宫中找出属于你自己的 救赎之道 吗?
上图为一座示例迷宫和一条可行的 通路。
题目描述
我们可以将迷宫抽象地表示为一个长 行,宽 列的 矩阵。其中 代表可通行的格子, 代表有方块阻拦的格子。矩阵以外的范围默认都是基岩,不可通行。给定 起点 的坐标 和 终点 的坐标 ,保证 起点 和 终点 对应的格子都没有方块阻拦。
如果玩家每次只能移动到 前,后,左,右 四个方向之一的相邻格子上(或者说不能斜着走),试着确定从 起点 到 终点 是否 存在通路。
输入格式
输入共 行。
第 行 个由空格隔开的整数 ,代表长 行,宽 列的迷宫起点为 ,终点为 。
接下来的 行,每行 个由空格隔开的数字 或 ,代表对应格子的通行情况。
输出格式
如果 起点 和 终点 之间 存在通路,输出 yes
,否则输出 no
。
答案对大小写不敏感,举例来说,Yes
,yEs
和 YES
都将被视为 yes
。
4 3 1 1 4 3
0 1 1
0 0 1
1 0 0
1 1 0
yes
4 3 1 1 4 3
0 1 1
0 0 1
1 1 0
1 1 0
no
3 3 1 1 3 3
0 1 1
0 0 0
1 1 0
yes
提示
样例 中,要从 走到 ,一条可行的路径是 $(1, 1) \to (2, 1) \to (2, 2) \to (3, 2) \to (3, 3) \to (4, 3)$。
样例 除了位于 的格子被加上了障碍方块外,其他数据与样例 完全一致。而加上这个方块后,唯一一条可行路径就被堵死了。
数据规模与约定
对于全部的测试点,保证 ,,,。且对于矩阵 ,保证 。
相关
在下列比赛中: