P14098 [POCamp 2022] 狼抓兔子 II / Djur

在一个有 $R \times C$ 的网格中，狼站在格子 $(1, 1)$，兔子站在格子 $(R, C)$。狼想走到格子 $(R, C)$，兔子想走到格子 $(1, 1)$。不过有一个问题：如果两条路径彼此相交，狼就会沿着兔子的路径去追它。现在我们想知道：给定网格的样子，能否为兔子和狼各找到一条不相交的路径？起点与终点格子（$(1, 1)$ 和 $(R, C)$）不计入路径。

第一行包含两个整数：$R, C$。在所有测试中，满足 $2 \le R \cdot C \le 2 \cdot 10^5$。 接下来给出一个 $R \times C$ 的网格。每个格子要么是 `.`，表示空格子；要么是 `#`，表示障碍。 保证格子 $(1, 1)$ 和 $(R, C)$ 是空的。

如果不存在两条满足要求的路径，输出 `NO`。 否则输出一行 `YES`。然后输出一个网格，其中用 `K` 标记兔子的路径，用 `V` 标记狼的路径。注意，所有障碍在输出时必须仍为障碍，所有不在路径上的空格子必须仍为空格子。每一条路径必须是连通的。 如果你使用 `C++`，为避免在正确解上出现 `Time Limit Exceeded`，建议使用 `\n` 而不是 `endl`。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | 1 | 9 | 没有障碍 | | 2 | 10 | $R \cdot C \le 10$ | | 3 | 20 | $R = 3$ | | 4 | 25 | $R \cdot C \le 1000$，并且保证存在一种解，其中狼只向下与向右移动，兔子只向上与向左移动 | | 5 | 36 | 无额外限制 |