← 返回题目列表

Codeforces · 2161/B

B. 建立连接

中文机器翻译题面 查看原题

给你一个 $$$n \times n$$$ 网格,其中一些单元格为黑色,其余为白色。您可以将一些白色单元格涂成黑色,以达到以下条件:

  1. 至少有一个黑色单元格。
  2. 所有黑色单元格必须正交连接,也就是说,在访问时应该可以通过跨越多个垂直或水平单元格边界从任何黑色单元格到达任何其他单元格 只有黑色 细胞。 你不能直接穿过牢房的角落。
  3. 没有三个连续的黑色单元格垂直或水平对齐。

您不能将黑色单元格涂成白色。

确定是否可以将一些白色单元格涂成黑色以满足所有条件。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 网格的大小。

以下 $$$n$$$ 行每行包含 $$$n$$$ 个字符 — 网格描述,其中每个字符代表一个单元格:

  • . — 一个白细胞;
  • # — 黑色单元格。

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

输出

对于每个测试用例,打印“是“是否可以将一些白色单元格涂成黑色以满足所有条件,并且”NO”否则。

您可以以任何大小写(大写或小写)打印每个字母。例如,字符串“是", "是的", "是“,和”是”将全部被识别为肯定答案。

示例

输入
复制

11
1
.
1
#
3
.##
.##
...
3
#..
.#.
..#
3
###
...
...
3
#.#
...
.#.
4
####
#..#
#..#
####
3
..#
...
.#.
3
..#
#..
...
5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
5
...#.
...#.
.....
##...
.....

输出
复制

YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES

注意

在第一个测试用例中,没有黑色单元格,因此我们必须将一个单元格涂成黑色。

在第二个和第三个测试用例中,网格从一开始就满足所有条件。

在第四个测试用例中,可能的解决方案之一是:

##.
.##
..#

在第五个测试用例中,网格违反了“三个连续的黑色单元格不应垂直或水平对齐”从一开始就有这种情况,所以没有解决办法。

在第六个测试用例中,可以证明,在不违反三个连续黑色单元格的条件的情况下,不可能实现连接的网格。