102412: [AtCoder]ABC241 C - Connect 6

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

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

Input

题意翻译

有一个 $N\times N$ 的棋盘网格用 $N$ 行字符串 $S_i$ 来表示。如果 $S_{i,j}$ 是 `#`,说明棋盘的第 $i$ 行第 $j$ 列有一个棋子,否则如果 $S_{i,j}$ 是 `.`,说明没有棋子。 请你判断是否可以再加入最多两个棋子使得棋盘存在六子连。六子连的定义是,存在某行、某列或者某对角线上有连续的六个棋子。

Output

得分:300分

问题描述

有一个由$N$行$N$列构成的网格,每个方格都被涂成白色或黑色。
网格的状态由$N$个字符串$S_i$表示。如果字符串$S_i$的第$j$个字符是#,则从上数第$i$行、从左数第$j$列的方格被涂成黑色。如果字符是.,则方格被涂成白色。

高桥可以选择最多两个涂成白色的方格,并将它们涂成黑色。
确定是否有可能使网格包含至少$6$个连续的涂成黑色的方格,它们可以按垂直、水平或对角线排列。这里,我们说网格包含至少$6$个连续的涂成黑色的方格按对角线排列,是指$N$行$N$列的网格完全包含一个$6$行$6$列的子网格,使得该子网格的至少一条对角线上所有方格都被涂成黑色。

限制条件

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

输入

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

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

输出

如果可以通过最多涂两个方格来满足条件,则输出Yes;否则,输出No


样例输入1

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

样例输出1

Yes

通过将从上数第3行的第3个方格和第6个方格涂成黑色,将有6个方格按水平方向涂成黑色。


样例输入2

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

样例输出2

Yes

虽然高桥无法选择一个方格涂成黑色,但网格已经满足了条件。


样例输入3

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

加入题单

上一题 下一题 算法标签: