/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 行 N 列のマス目があり、それぞれのマスは白または黒で塗られています。
マス目の状態は N 個の文字列 S_i で表され、
S_i の j 文字目が # であることはマス目の上から i 行目、左から j 列目のマスが黒く塗られていることを、
. であることは白く塗られていることをさします。
高橋君はこのマス目のうち高々 2 つの白く塗られているマスを選び、黒く塗ることができます。
マス目の中に、黒く塗られたマスが縦、横、ななめのいずれかの向きに 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
出力
高々 2 つのマス目を黒く塗ることで条件をみたすようにできるなら Yes を、そうでないならば No を出力せよ。
入力例 1
8 ........ ........ .#.##.#. ........ ........ ........ ........ ........
出力例 1
Yes
上から 3 行目の左から 3, 6 番目のマスを塗ることで横方向に 6 つの黒く塗られたマスを連続させることができます。
入力例 2
6 ###### ###### ###### ###### ###### ######
出力例 2
Yes
高橋君はマス目を新たに黒く塗ることはできませんが、すでにこのマス目は条件をみたしています。
入力例 3
10 .......... #..##..... .......... .......... ....#..... ....#..... .#...#..#. .......... .......... ..........
出力例 3
No
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