← 返回题目列表

Codeforces · 1949/J

J. 阿曼达变形虫

中文机器翻译题面 查看原题

这个问题有一个附件。您可以用它来模拟和可视化阿米巴的运动。

阿米巴阿曼达生活在方形像素的矩形网格内。她的身体占据了其中一些像素。其他像素可能是空闲的或被阻止的。阿曼达使用所谓的变形虫运动穿过网格。在这样的运动的每一步中,她的身体首先缩小一个像素(身体的一个像素被移除并变得自由),然后在不同的地方生长(一个先前自由的像素被添加到身体)。

为了防止结构损坏,阿曼达的身体始终占据像素的连接区域,这意味着形成身体的任何一对像素都可以通过一系列相邻像素连接,而无需离开身体。如果两个像素共享公共边(每个像素最多有 4 个相邻像素),则它们被视为相邻。即使在移动过程中,身体也保持连接,包括删除一个像素之后和添加另一个像素之前的那一刻。

你的任务是帮助阿曼达找到出路。给定她的初始位置和期望的最终位置,建议从前者到后者的一系列有效动作。

示例$$$1$$$说明:填充形状为初始位置,虚线区域为最终位置。

输入

第一行包含两个整数 $$$r$$$ 和 $$$c$$$ ($$$1\le r,c \le 50$$$) - 矩形网格的大小(以像素为单位)。

接下来的 $$$r$$$ 行每行包含 $$$c$$$ 个字符,描述 Amanda 的初始位置。这些字符中的每一个都是点 $$$\texttt{.}$$$ 表示空闲像素,星号 $$$\texttt{*}$$$ 表示阿曼达的身体,或者 $$$\texttt{X}$$$ 表示可能永远不会被占用的阻塞像素。

下一行为空。

接下来的 $$$r$$$ 行以与初始位置相同的格式描述所需的最终位置。

保证:

- 两个位置形成阿曼达身体的像素数相同,且至少为 2。
- 阿曼达的身体在初始位置连接。
- 阿曼达的身体在最终位置连接。
- 被阻挡的像素在初始位置和最终位置的描述之间不会改变,它们的位置在两个位置中完全相同。

输出

如果 Amanda 有可能从初始位置移动到最终位置,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。

如果可能,在下一行打印一个整数 $$$m$$$ ($$$0\le m\le 10\,000$$$) — 要执行的移动次数。

以下 $$$m$$$ 行每行必须包含四个整数坐标:$$$i_1$$$、$$$j_1$$$、$$$i_2$$$、$$$j_2$$$ ($$$1\le i_1,i_2\le r$$$、$$$1\le j_1,j_2\le c$$$)。这四个坐标指定一次移动,这意味着第 $$$i_1$$$ 行和 $$$j_1$$$ 列的像素首先从主体中删除。然后,$$$(i_2,j_2)$$$ 必须指定添加一个像素的不同位置。

该序列应仅包含有效的移动,并且在最后移动之后,阿曼达的身体应占据所需的最终位置。

如果有多个解决方案,请打印其中任何一个。

在这个问题的假设下,可以证明,如果阿曼达有可能从初始位置移动到期望的最终位置,那么最多可以通过 $$$10\,000$$$ 移动来完成。

示例

输入 #1

5 8
.******.
**.X**..
*******.
**.X**..
.******.
.******.
...X****
.*******
...X****
.******.

输出 #1

YES
5
3 1 3 8
2 1 2 8
4 1 4 8
2 2 4 7
4 2 2 7

输入 #2

2 5
*.X..
**X..
..X**
..X*.

输出 #2

NO

注意

在第一个示例中,Amanda 执行了 5 步以到达最终位置,如下图所示。