P13570 [CCPC 2024 重庆站] 连方

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

给定正整数 $n$ 和两个仅包含字符 `.` 和 `#` 的长度为 $n$ 的字符串 $a, b$，请构造一个 $7\times n$ 的仅包含字符 `.` 与 `#` 的矩阵，满足以下条件： - 矩阵第 $1$ 行与 $a$ 相同，第 $7$ 行与 $b$ 相同。 - 由四方向连通的 `#` 构成的图形均为**实心的**矩形。具体地： - 对于两个 `#` 字符，如果可以从其中一个 `#` 字符出发，在有限步之内仅经过 `#` 字符到达另一个 `#` 字符，其中每一步均为向**上、左、下、右四个方向**之一移动一格，则称这两个 `#` 字符在同一组。那么，由同一组内的所有 `#` 字符构成的图形均为**实心的**矩形。 - 所有的 `#` 字符八方向连通，具体地： - 对于任意两个 `#` 字符，均可以从其中一个 `#` 字符出发，在有限步之内仅经过 `#` 字符到达另一个 `#` 字符，其中每一步均为向**上、左、下、右、左上、右上、左下、右下八个方向**之一移动一格。 请输出任意一个满足条件的矩阵，或判定无解。

输入的第一行包含一个正整数 $T \ (1\le T \le 10^4)$，代表数据组数。 每组数据第一行包含一个正整数 $n \ (2\le n \le 10^5)$，代表矩阵的宽度。 接下来两行分别包含仅包含字符 `.` 与 `#`，长度为 $n$ 的两个字符串 $a, b$，代表矩阵的第 $1$ 行与第 $7$ 行。 保证 $a$ 与 $b$ 均包含至少一个 `#`。 保证单个测试点内所有 $n$ 的总和不超过 $2\times10^5$。

对于每组测试数据，如果不存在满足要求的矩阵，则输出一行一个字符串 `No`。 如果存在满足要求的矩阵，则先输出一行一个字符串 `Yes`，然后输出 $7$ 行，每行包含一个长度为 $n$ 的字符串，代表你构造的矩阵。

对于第一组数据，以下是另一种正确答案： ``` #..# #..# #..# .##. #..# #..# .##. ``` 但以下矩阵不是正确答案，因为由 $(1,1)(2,1)(2,2)$ 这组四方向连通的 `#` 字符构成的图形不是矩形。对于 $(4,1)(4,2)(5,1)(6,1)$ 这组四方向连通的 `#` 字符同理。 ``` #..# ##.# ..#. ##.# #.#. #..# .##. ``` 同样，以下矩阵也不是正确答案，因为位于 $(1,1)$ 的 `#` 字符与其他 `#` 字符不满足八方向连通的条件。 ``` #..# ...# ...# ...# ...# ...# .##. ```