#P18248. The Witness
The Witness
The Witness
题目描述
Bobo 平时很喜欢解谜游戏。他最喜欢的游戏是 Jonathan Blow 设计、于 2016 年发行的《The Witness》。游戏中包含九种主要谜题及若干隐藏的环境谜题,共有 664 个谜题分布在开放世界中,玩家需要探索世界,推理出各种谜题的规则。
其中,Bobo 擅长一种称为“黑白方格”的谜题。谜题位于矩形网格上,要求画出一条从指定起点到指定终点的简单网格路径,将不同颜色的方格分隔开。
下面给出了原游戏中的六组谜题及其一种解答。每组左图是谜题,右图是解答;起点用圆点表示,终点是从网格向外凸出的小段。
| 谜题 | 一种解答 |
|---|---|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
现在,Bobo 给你一个每个方格都为黑色或白色的“黑白方格”谜题,请你构造一种合法解答,或判断它无解。
形式化地,谜题包含:
- 一个 行、 列的矩形网格,共有 个方格和 个网格顶点。
- 每个方格的颜色为黑色或白色。
- 网格边界上的两个不同顶点,分别作为起点 和终点 。
左上角顶点的坐标为 ,右下角顶点的坐标为 。第一维坐标沿行向下增加,第二维坐标沿列向右增加。顶点 在边界上,当且仅当 、、、 中至少一个条件成立。
一个合法解答是一条路径
$$P=((x_1,y_1),(x_2,y_2),\ldots,(x_\ell,y_\ell)),\qquad\ell\ge2,$$满足以下全部条件:
- 第一个顶点为起点,最后一个顶点为终点。
- 相邻两个顶点在网格中相邻,即 。
- 路径是简单路径:不会重复经过任何网格顶点。
- 网格被路径分隔出的每个区域中,只能含有一种颜色的方格。
路径允许沿网格边界行走。
输入格式
第一行包含两个整数 。
接下来 行,每行包含一个长度为 的字符串,只包含字符 B 和 W。第 行第 个字符表示第 行、第 列方格的颜色,B 表示黑色,W 表示白色。
最后一行包含四个整数 ,表示起点和终点。
输出格式
若谜题无解,输出一行 NO。
否则,第一行输出 YES,第二行输出路径的顶点数 。接下来 行,第 行输出顶点坐标 。
如果存在多个合法方案,输出任意一个即可。YES 和 NO 的字母大小写不限,例如 yES、yes、Yes 都会被识别为肯定回答。
数据范围
- 。
- ,。
- 起点和终点都在网格边界上,且互不相同。
- 所有方格的颜色均为
B或W。
样例 1
3 3
BBB
BWB
WWW
3 0 0 3
YES
9
3 0
2 0
2 1
1 1
1 2
2 2
2 3
1 3
0 3
样例 2
1 1
W
0 0 1 1
YES
3
0 0
1 0
1 1
样例 3
2 2
WB
BW
0 0 2 2
NO
样例说明
第一组样例对应题目中第五组图片的谜题。
第二组样例还可以输出路径 。











