A16689. Make Connected
编程题
普及/提高-
知识点
题目描述
给你一个 $n \times n$ 的网格，其中一些格子被涂成黑色，其余格子为白色。你可以将部分白色格子涂黑，使得最终满足以下条件：
1. 至少存在一个黑色格子。
2. 所有黑色格子是正交连通的，即从任意一个黑色格子出发，只经过若干条水平或垂直边且只经过黑色格子，可以到达任意另一个黑色格子。你不能直接通过格子的对角线连通。
3. 不存在三个垂直或水平连续排列的黑色格子。
你不能将黑色格子涂白。
请判断是否可以通过涂黑一些白色格子，使得上述条件均得到满足。
1. 至少存在一个黑色格子。
2. 所有黑色格子是正交连通的，即从任意一个黑色格子出发，只经过若干条水平或垂直边且只经过黑色格子，可以到达任意另一个黑色格子。你不能直接通过格子的对角线连通。
3. 不存在三个垂直或水平连续排列的黑色格子。
你不能将黑色格子涂白。
请判断是否可以通过涂黑一些白色格子，使得上述条件均得到满足。
输入格式
每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。
每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示网格的大小。
接下来的 $n$ 行中，每行包含 $n$ 个字符，描述网格的状态。每个字符代表一个格子：
-
-
保证所有测试用例中 $n$ 的总和不超过 $2000$。
每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示网格的大小。
接下来的 $n$ 行中，每行包含 $n$ 个字符，描述网格的状态。每个字符代表一个格子：
-
. 表示白色格子；-
# 表示黑色格子。保证所有测试用例中 $n$ 的总和不超过 $2000$。
输出格式
对于每个测试用例，如果存在一种方法可以将部分白色格子涂黑，使得所有条件都满足，则输出 “YES”；否则输出 “NO”。
你可以以任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被视为正确答案。
你可以以任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被视为正确答案。
输入输出样例
输入 #1
11 1 . 1 # 3 .## .## ... 3 #.. .#. ..# 3 ### ... ... 3 #.# ... .#. 4 #### #..# #..# #### 3 ..# ... .#. 3 ..# #.. ... 5 #.#.# .#.#. #.#.# .#.#. #.#.# 5 ...#. ...#. ..... ##... .....
输出 #1
YES YES YES YES NO NO NO YES YES NO YES
说明/提示
在第一个测试用例中，初始没有黑色格子，因此必须涂黑至少一个格子。
在第二个和第三个测试用例中，初始网格已经满足所有条件。
在第四个测试用例中，其中一种可行的方案为：
```
##.
.##
..#
```
在第五个测试用例中，初始网格已经存在三连黑格，违反条件三，因此无解。
在第六个测试用例中，可以证明无法在不违反三个连续黑格条件下，使所有黑格连通。
由 ChatGPT 5 翻译
在第二个和第三个测试用例中，初始网格已经满足所有条件。
在第四个测试用例中，其中一种可行的方案为：
```
##.
.##
..#
```
在第五个测试用例中，初始网格已经存在三连黑格，违反条件三，因此无解。
在第六个测试用例中，可以证明无法在不违反三个连续黑格条件下，使所有黑格连通。
由 ChatGPT 5 翻译