#P18248. The Witness

The Witness

The Witness

题目描述

Bobo 平时很喜欢解谜游戏。他最喜欢的游戏是 Jonathan Blow 设计、于 2016 年发行的《The Witness》。游戏中包含九种主要谜题及若干隐藏的环境谜题,共有 664 个谜题分布在开放世界中,玩家需要探索世界,推理出各种谜题的规则。

其中,Bobo 擅长一种称为“黑白方格”的谜题。谜题位于矩形网格上,要求画出一条从指定起点到指定终点的简单网格路径,将不同颜色的方格分隔开。

下面给出了原游戏中的六组谜题及其一种解答。每组左图是谜题,右图是解答;起点用圆点表示,终点是从网格向外凸出的小段。

谜题 一种解答
第1组谜题 第1组解答
第2组谜题 第2组解答
第3组谜题 第3组解答
第4组谜题 第4组解答
第5组谜题 第5组解答
第6组谜题 第6组解答

现在,Bobo 给你一个每个方格都为黑色或白色的“黑白方格”谜题,请你构造一种合法解答,或判断它无解。

形式化地,谜题包含:

  • 一个 nn 行、mm 列的矩形网格,共有 n×mn\times m 个方格和 (n+1)×(m+1)(n+1)\times(m+1) 个网格顶点。
  • 每个方格的颜色为黑色或白色。
  • 网格边界上的两个不同顶点,分别作为起点 (sx,sy)(s_x,s_y) 和终点 (ex,ey)(e_x,e_y)。

左上角顶点的坐标为 (0,0)(0,0),右下角顶点的坐标为 (n,m)(n,m)。第一维坐标沿行向下增加,第二维坐标沿列向右增加。顶点 (x,y)(x,y) 在边界上,当且仅当 x=0x=0、x=nx=n、y=0y=0、y=my=m 中至少一个条件成立。

一个合法解答是一条路径

$$P=((x_1,y_1),(x_2,y_2),\ldots,(x_\ell,y_\ell)),\qquad\ell\ge2,$$

满足以下全部条件:

  • 第一个顶点为起点,最后一个顶点为终点。
  • 相邻两个顶点在网格中相邻,即 ∣xi−xi−1∣+∣yi−yi−1∣=1|x_i-x_{i-1}|+|y_i-y_{i-1}|=1。
  • 路径是简单路径:不会重复经过任何网格顶点。
  • 网格被路径分隔出的每个区域中,只能含有一种颜色的方格。

路径允许沿网格边界行走。

输入格式

第一行包含两个整数 n,mn,m。

接下来 nn 行,每行包含一个长度为 mm 的字符串,只包含字符 B 和 W。第 ii 行第 jj 个字符表示第 ii 行、第 jj 列方格的颜色,B 表示黑色,W 表示白色。

最后一行包含四个整数 sx,sy,ex,eys_x,s_y,e_x,e_y,表示起点和终点。

输出格式

若谜题无解,输出一行 NO。

否则,第一行输出 YES,第二行输出路径的顶点数 ℓ\ell。接下来 ℓ\ell 行,第 ii 行输出顶点坐标 xi,yix_i,y_i。

如果存在多个合法方案,输出任意一个即可。YES 和 NO 的字母大小写不限,例如 yES、yes、Yes 都会被识别为肯定回答。

数据范围

  • 1≤n,m≤401\le n,m\le40。
  • 0≤sx,ex≤n0\le s_x,e_x\le n,0≤sy,ey≤m0\le s_y,e_y\le m。
  • 起点和终点都在网格边界上,且互不相同。
  • 所有方格的颜色均为 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

样例说明

第一组样例对应题目中第五组图片的谜题。

第二组样例还可以输出路径 ((0,0),(0,1),(1,1))((0,0),(0,1),(1,1))。