Cactus Wall

题意翻译

为了抵御怪物的袭击，Monocarp 决定利用他的院子构建一座仙人掌屏障。院子可以看作 $n$ 行 $m$ 列的网格，每个格子内最多可以种一颗仙人掌。 怪物可以从第一行任意一个没有仙人掌的格子进入院子，它每次能走到一个**四联通相邻**（即两个格子有公共边）且没有仙人掌的格子。如果怪物怎么走都无法到达最后一行的某个没有仙人掌的格子，那么院子里就成功构建了一座屏障。 但如果仙人掌种植过密，就可能因为缺乏养分凋零而失去作用，因此**任意两个四联通相邻的格子不能同时种上仙人掌**。 现在可能有些格子已经种上了仙人掌。Monocarp 想要知道在**不铲除已有仙人掌**的前提下，至少要再种多少颗仙人掌才能构成一座屏障。 ### 输入格式 第一行一个整数 $t$，数据组数。 对于每组数据，第一行两个数 $n$，$m$，院子的大小。接下来是 $n$ 行 $m$ 列的字符矩阵，`#` 表示这个格子已经有仙人掌，`.` 表示没有仙人掌。 ### 输出格式 对于每组数据，如果无法建成屏障，输出一行 `NO`。 否则先输出一行 `YES`，再输出 $n$ 行 $m$ 列的字符矩阵，表示任意一组建成屏障的最优解，格式同输入。 ### 数据范围 $1\leq t\leq 10^3$，$2\leq n,m\leq 2\times10^5$，$\sum nm\leq 4\times10^5$

题目描述

Monocarp is playing Minecraft and wants to build a wall of cacti. He wants to build it on a field of sand of the size of $ n \times m $ cells. Initially, there are cacti in some cells of the field. Note that, in Minecraft, cacti cannot grow on cells adjacent to each other by side — and the initial field meets this restriction. Monocarp can plant new cacti (they must also fulfil the aforementioned condition). He can't chop down any of the cacti that are already growing on the field — he doesn't have an axe, and the cacti are too prickly for his hands. Monocarp believes that the wall is complete if there is no path from the top row of the field to the bottom row, such that: - each two consecutive cells in the path are adjacent by side; - no cell belonging to the path contains a cactus. Your task is to plant the minimum number of cacti to build a wall (or to report that this is impossible).

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — number of test cases. The first line of each test case contains two integers $ n $ and $ m $ ( $ 2 \le n, m \le 2 \cdot 10^5 $ ; $ n \times m \le 4 \cdot 10^5 $ ) — the number of rows and columns, respectively. Then $ n $ rows follow, $ i $ -th row contains a string $ s_i $ of length $ m $ , where $ s_{i, j} $ is '\#', if a cactus grows at the intersection of the $ i $ -th row and the $ j $ -th column. Otherwise, $ s_{i, j} $ is '.'. The sum of $ n \times m $ over all test cases does not exceed $ 4 \cdot 10^5 $ .

输出格式

For each test case, print NO in the first line if it is impossible to build a cactus wall without breaking the rules. Otherwise, print YES in the first line, then print $ n $ lines of $ m $ characters each — the field itself, where the $ j $ -th character of the $ i $ -th line is equal to '\#', if there is a cactus on the intersection of the $ i $ -th row and the $ j $ -th column, otherwise it is '.'. If there are multiple optimal answers, print any of them.

输入输出样例

输入样例 #1

4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...

输出样例 #1

YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...

**题目大意：**
Monocarp 想要在他 $n \times m$ 的沙地院子里建一个仙人掌墙。院子里已经有仙人掌在一些格子上，但按照 Minecraft 的规则，仙人掌不能种在相邻的格子上。Monocarp 可以在不违反规则的前提下种新的仙人掌，但不能砍掉已有的仙人掌。如果从第一行到最后一行不存在一条不经过仙人掌的路径，那么仙人掌墙就建成了。现在要求计算最少需要种多少仙人掌才能建成仙人掌墙，或者报告这是不可能的。

**输入格式：**
第一行包含一个整数 $t$，表示数据组数。
每组数据第一行包含两个整数 $n$ 和 $m$，表示院子的大小。
接下来是 $n$ 行，每行包含一个长度为 $m$ 的字符串，由 `.` 和 `#` 组成，其中 `.` 表示这个格子没有仙人掌，`#` 表示有仙人掌。

**输出格式：**
对于每组数据，如果无法建成仙人掌墙，输出一行 `NO`。
否则先输出一行 `YES`，然后输出 $n$ 行 $m$ 列的字符矩阵，表示任意一组建成仙人掌墙的最优解，格式同输入。

**数据范围：**
$1 \leq t \leq 10^3$，$2 \leq n, m \leq 2 \times 10^5$，$\sum nm \leq 4 \times 10^5$**题目大意：** Monocarp 想要在他 $n \times m$ 的沙地院子里建一个仙人掌墙。院子里已经有仙人掌在一些格子上，但按照 Minecraft 的规则，仙人掌不能种在相邻的格子上。Monocarp 可以在不违反规则的前提下种新的仙人掌，但不能砍掉已有的仙人掌。如果从第一行到最后一行不存在一条不经过仙人掌的路径，那么仙人掌墙就建成了。现在要求计算最少需要种多少仙人掌才能建成仙人掌墙，或者报告这是不可能的。 **输入格式：** 第一行包含一个整数 $t$，表示数据组数。 每组数据第一行包含两个整数 $n$ 和 $m$，表示院子的大小。 接下来是 $n$ 行，每行包含一个长度为 $m$ 的字符串，由 `.` 和 `#` 组成，其中 `.` 表示这个格子没有仙人掌，`#` 表示有仙人掌。 **输出格式：** 对于每组数据，如果无法建成仙人掌墙，输出一行 `NO`。 否则先输出一行 `YES`，然后输出 $n$ 行 $m$ 列的字符矩阵，表示任意一组建成仙人掌墙的最优解，格式同输入。 **数据范围：** $1 \leq t \leq 10^3$，$2 \leq n, m \leq 2 \times 10^5$，$\sum nm \leq 4 \times 10^5$