连线 6

题目描述

有一个 $N$ 行 $N$ 列的网格,每个格子被涂成白色或黑色。

网格的状态由 $N$ 个字符串 $S_i$ 表示。 如果 $S_i$ 的第 $j$ 个字符是 #,则从上数第 $i$ 行、从左数第 $j$ 列的格子是黑色。 如果字符是 .,则该格子是白色。

高桥可以选择至多两个为白色的格子,将它们涂成黑色。

判断是否有可能使网格中出现 $6$ 个或更多连续涂黑的格子,排列方向为竖直、水平或对角线。

这里,如果这个 $N$ 行 $N$ 列的网格完整地包含某个 $6$ 行 $6$ 列的子网格,且该子网格至少有一条对角线上的所有格子都是黑色,则称该网格在对角线方向上含有 $6$ 个或更多连续涂黑的格子。

输入格式

输入按以下格式从标准输入给出:

N
S_1
S_2
⋮
S_N

输出格式

如果通过至多涂黑两个格子能够满足条件,输出 Yes;否则输出 No。

样例

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

Yes

通过把从上数第 $3$ 行、从左数第 $3$ 个和第 $6$ 个格子涂黑,将有 $6$ 个黑色格子水平排列。

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

Yes

高桥无需涂黑任何格子,网格本身已经满足条件。

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

No

数据范围

• $6 \le N \le 1000$
• $\lvert S_i \rvert = N$
• $S_i$ 由 # 和 . 组成。