#4175. 「CEOI2024」玩具谜题

题目描述

题目译自 CEOI 2024 Day2 T1「Toy」

CEOI 2024 的命题人 Ben 从科学委员会收到了一份礼物——一个玩具。这个玩具是个谜题，可以想象成一个 $H$ 行 $W$ 列的网格，上面放着一个金属物体。这个金属物体由两部分组成：一个横向的 $1$ 行 $K$ 列的部分和一个纵向的 $L$ 行 $1$ 列的部分，这两部分松散地连接在一起。它们都不能旋转，但可以在网格内水平或垂直滑动，只要它们始终重叠在一个方格上。

网格里还有一些障碍物。金属物体的任何部分都不能穿过障碍物，更糟糕的是，它们也不能（即使部分）移出网格。Ben 的任务是将金属物体从指定起始位置移动到（可能不同的）目标位置，使得两部分重叠在指定的目标方格上。

然而，Ben 玩这个玩具已经有一段时间了，还没有解开谜题。事实上，他开始怀疑组织者在捉弄他，给了他一个无解的谜题。因此，他向你求助，想知道这个谜题是否有解。

---

输入格式

输入的第一行包含四个空格分隔的整数 $W$, $H$, $K$, $L$，分别表示谜题的宽度、高度、横向部分的宽度和纵向部分的高度。
第二行包含四个整数 $x_h$, $y_h$, $x_v$, $y_v$，表示横向部分最左上角方格的坐标和纵向部分最左上角方格的坐标。

• 行从上到下编号为 $0$ 到 $H-1$，列从左到右编号为 $0$ 到 $W-1$。
• $x$ 坐标表示列号，$y$ 坐标表示行号。

接下来的 $H$ 行每行包含 $W$ 个字符，表示网格。字符 . 表示空方格，字符 X 表示障碍物，字符 * 表示目标方格。

保证金属物体的初始位置合法，即两部分重叠在一个方格上，并且两部分不与障碍物重叠也不超出网格。

只有一个目标方格，即玩具中只有一个字符 *，它可能与金属物体的初始位置重叠。

---

输出格式

如果可以将金属物体移动到目标方格，则输出一行 YES，否则输出 NO。

---

样例 1

输入

4 3 2 2
0 1 0 0
.X.*
....
...X

输出

YES

解释
初始状态如下：

我们可以先将纵向部分向下移动一格，然后尽可能地交替移动横向和纵向部分，直到无法继续。接着，我们可以将纵向部分向上并向右移动，到达目标方格，最后将横向部分向上移动，也到达目标方格。

---

样例 2

输入

2 3 2 3
0 1 0 0
.X
.*
.X

输出

NO

解释
无法移动纵向部分而不碰到障碍物，因此永远无法到达目标方格。

---

数据范围与提示

对于所有输入数据，满足：

• $2 \leq W, H \leq 1\,500$
• $2 \leq K \leq W$, $2 \leq L \leq H$
• $0 \leq x_h \leq W - K$, $0 \leq y_h \leq H - 1$
• $0 \leq x_v \leq W - 1$, $0 \leq y_v \leq H - L$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
1	$W, H \le 50$	$14$
2	$W, H \le 90$	$21$
3	$W, H \le 300$, $K, L \le 10$	$9$
4	$W, H \le 360$	$29$
5	无附加限制	$27$