题目描述

在一个有 $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。

2 2
.#
..

NO

3 3
...
.#.
...

YES
.VV
K#V
KK.

10 10
........##
..##.##.##
#....##...
###....##.
###.##.#..
#......###
#.###..###
#...#.....
#.#.#.....
########..

YES
.VVVV...##
KK##V##.##
#KKKV##...
###KVVV##.
###K##V#..
#..KKKV###
#.###KV###
#...#KVVVV
#.#.#KKKKV
########K.

4 7
.....##
..#....
..##...
.......

YES
.VVVV##
KK#.VVV
.K##..V
.KKKKK.

16 14
..............
..............
############..
...........#..
...........#..
..#######..#..
..#.....#..#..
..#.....#..#..
..#..#.....#..
..#..#.....#..
..#..#######..
..#...........
..#...........
..############
..............
..............

YES
.VVVVVVVVVVVVV
KKKKKKKKKKKKKV
############KV
KKKKKKKKKKK#KV
KVVVVVVVVVK#KV
KV#######VK#KV
KV#VVVVV#VK#KV
KV#VKKKV#VK#KV
KV#VK#KVVVK#KV
KV#VK#KKKKK#KV
KV#VK#######KV
KV#VKKKKKKKKKV
KV#VVVVVVVVVVV
KV############
KVVVVVVVVVVVVV
KKKKKKKKKKKKK.

提示

子任务

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