Score : $300$ points

问题描述

存在一个包含 $N$ 行横向和 $N$ 列纵向的网格，其中每个方格被涂成白色或黑色。

网格的状态由 $N$ 个字符串 $S_i$ 表示。如果 $S_i$ 的第 $j$ 个字符是 #，则从上到下第 $i$ 行、从左到右第 $j$ 列的方格被涂成黑色。如果字符是 ., 则该方格被涂成白色。

高桥最多可以选择两个白色方格，并将其涂成黑色。
判断是否存在一种可能性，使得网格中包含连续对齐（纵向、横向或对角线方向）的 $6$ 个或更多黑色方格。

这里，当网格完全包含一个具有 $6$ 行和 $6$ 列的子网格，且该子网格至少在一个对角线上所有方格都被涂成黑色时，我们称网格包含 $6$ 个或更多连续对齐的黑色方格（对角线方向）。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a grid with $N$ horizontal rows and $N$ vertical columns, where each square is painted white or black.
The state of the grid is represented by $N$ strings, $S_i$. If the $j$-th character of $S_i$ is #, the square at the $i$-th row from the top and the $j$-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain $6$ or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing $6$ or more consecutive squares painted black aligned diagonally if the grid with $N$ rows and $N$ columns completely contains a subgrid with $6$ rows and $6$ columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• $6 \leq N \leq 1000$
• $\lvert S_i\rvert =N$
• $S_i$ consists of # and ..

Input

Input is given from Standard Input in the following format:

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

If it is possible to fulfill the condition by painting at most two squares, then print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

By painting the $3$-rd and the $6$-th squares from the left in the $3$-rd row from the top, there will be $6$ squares painted black aligned horizontally.

Sample Input 2

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

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

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

Sample Output 3

No

update @ 2024/3/10 10:23:13