AT_abc241_c [ABC241C] Connect 6

题目描述

有一个 $N$ 行 $N$ 列的格子，每个格子被涂成黑色或白色。
格子的状态由 $N$ 个字符串 $S_i$ 表示，第 $i$ 个字符串的第 $j$ 个字符为 # 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子被涂成黑色，为 . 表示被涂成白色。

高桥君可以选择至多 $2$ 个白色格子，将其涂成黑色。
请判断是否可以通过这种方式，使得存在 $6$ 个或以上连续的黑色格子，这些格子可以是竖直、水平或斜向（对角线）方向连续。
其中，斜向 $6$ 个或以上连续的黑色格子，指的是在 $N$ 行 $N$ 列的格子中，存在一个完全包含于格子中的 $6$ 行 $6$ 列的子格子，使得该子格子的至少一条对角线上所有格子都被涂成黑色。

输入格式

输入按以下格式从标准输入读入。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

如果可以通过至多 $2$ 次涂黑操作使得满足条件，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

8
........
........
.#.##.#.
........
........
........
........
........

输出 #1

Yes

输入输出样例 #2

输入 #2

6
######
######
######
######
######
######

输出 #2

Yes

输入输出样例 #3

输入 #3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

输出 #3

No

说明/提示

限制

• $6 \leq N \leq 1000$
• $|S_i| = N$
• $S_i$ 仅由 # 和 . 组成。

样例解释 1

可以将第 $3$ 行第 $3$ 列和第 $3$ 行第 $6$ 列的格子涂黑，使得水平方向上有 $6$ 个连续的黑色格子。

样例解释 2

高桥君虽然不能再涂黑任何格子，但当前格子已经满足条件。

由 ChatGPT 4.1 翻译