#S1D12. Day12_救赎之道

Day12_救赎之道

题目背景

众所不周知,高中时 PC 长期沉迷于编写 Minecraft 服务器小游戏插件。其中,他对 “动态迷宫” 情有独钟。基本的原理是,在每次游戏开始时按给定大小,随机生成一座新的迷宫给玩家,而不是重复使用同一座。这样可以保证玩家每次游玩时要走的路线都不一样。

但由于当时的 PC 太笨了,随机生成的迷宫有概率会出现 入口出口 之间 没有通路 的情况。显然这对玩家很不友好,所以当出现这种情况时 PC 会选择重新生成迷宫,直到 存在通路 为止。那么,怎么才能确定 入口出口 间有没有通路呢?这个问题曾经困扰了 PC 许久,彼时形如 ChatGPT 的大语言模型还未像现如今这样家喻户晓。最终,PC 通过翻找各种技术帖和博客,找出了解决这个问题的办法。那么,如果你是 PC,你能想办法在一座迷宫中找出属于你自己的 救赎之道 吗?

上图为一座示例迷宫和一条可行的 通路

题目描述

我们可以将迷宫抽象地表示为一个长 nn 行,宽 mm 列的 0101 矩阵。其中 00 代表可通行的格子,11 代表有方块阻拦的格子。矩阵以外的范围默认都是基岩,不可通行。给定 起点 的坐标 (x1,y1)(x_1,y_1)终点 的坐标 (x2,y2)(x_2,y_2),保证 起点终点 对应的格子都没有方块阻拦。

如果玩家每次只能移动到 前,后,左,右 四个方向之一的相邻格子上(或者说不能斜着走),试着确定从 起点终点 是否 存在通路

输入格式

输入共 n+1n + 1 行。

1166 个由空格隔开的整数 n,m,x1,y1,x2,y2n, m, x_1, y_1, x_2, y_2,代表长 nn 行,宽 mm 列的迷宫起点为 (x1,y1)(x_1,y_1),终点为 (x2,y2)(x_2,y_2)

接下来的 nn 行,每行 mm 个由空格隔开的数字 0011,代表对应格子的通行情况。

输出格式

如果 起点终点 之间 存在通路,输出 yes ,否则输出 no

答案对大小写不敏感,举例来说,YesyEsYES 都将被视为 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

提示

样例 11 中,要从 (1,1)(1, 1) 走到 (4,3)(4, 3),一条可行的路径是 $(1, 1) \to (2, 1) \to (2, 2) \to (3, 2) \to (3, 3) \to (4, 3)$。

样例 22 除了位于 (3,2)(3,2) 的格子被加上了障碍方块外,其他数据与样例 11 完全一致。而加上这个方块后,唯一一条可行路径就被堵死了。

数据规模与约定

对于全部的测试点,保证 1x1,x2n1031 \leq x_1,x_2 \leq n \leq 10^31y1,y2m1031 \leq y_1,y_2 \leq m \leq 10^3x1x2x_1 \neq x_2y1y2y_1 \neq y_2。且对于矩阵 aa,保证 ax1y1=ax2y2=0a_{x_1y_1} = a_{x_2y_2} = 0