← 返回题目
题库练习 Make Connected
← 上一题 下一题 →

A16689 | Make Connected

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

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

你不能将黑色格子涂白。

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

输入格式

每个测试点包含多组测试用例。第一行包含一个整数 $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
C++ 编辑器
输入
输出