P10804 [CEOI 2024] 玩具谜题

**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day2 T1「[Toy](https://ceoi2024.fi.muni.cz/page/tasks/statements/toy.pdf)」** 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** 初始状态如下：  我们可以先将纵向部分向下移动一格，然后尽可能地交替移动横向和纵向部分，直到无法继续。接着，我们可以将纵向部分向上并向右移动，到达目标方格，最后将横向部分向上移动，也到达目标方格。 **样例解释 2** 无法移动纵向部分而不碰到障碍物，因此永远无法到达目标方格。 对于所有输入数据，满足： - $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$ |