CFCF2161B.Make Connected

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个 $n \times n$ 的网格，其中一些格子被涂成黑色，其余格子为白色。你可以将部分白色格子涂黑，使得最终满足以下条件：

至少存在一个黑色格子。
所有黑色格子是正交连通的，即从任意一个黑色格子出发，只经过若干条水平或垂直边且只经过黑色格子，可以到达任意另一个黑色格子。你不能直接通过格子的对角线连通。
不存在三个垂直或水平连续排列的黑色格子。

你不能将黑色格子涂白。

请判断是否可以通过涂黑一些白色格子，使得上述条件均得到满足。

输入格式

每个测试点包含多组测试用例。第一行包含一个整数 $t$ （ $1 \leq t \leq 1000$ ），表示测试用例的数量。

每组测试用例的第一行包含一个整数 $n$ （ $1 \leq n \leq 100$ ），表示网格的大小。

接下来的 $n$ 行中，每行包含 $n$ 个字符，描述网格的状态。每个字符代表一个格子：

. 表示白色格子；
# 表示黑色格子。

保证所有测试用例中 $n$ 的总和不超过 $2000$ 。

输出格式

对于每个测试用例，如果存在一种方法可以将部分白色格子涂黑，使得所有条件都满足，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写输出答案。例如，"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 翻译

首页