← 返回题目列表

AtCoder · past18_h

H. 找到C!

中文机器翻译题面 查看原题

问题陈述

像这样的网格上的对象称为 C.

###  ####  #####
#..  #...  #....
###  #...  #....
     ####  #....
           #####

上图所示为 C级别 1, 2,和 3,从左到右。

形式上,对于正整数 l,一个 C* 级别 l 定义如下。

  • A C 级别 l 是 (l+2) \times (l+2) 方格。
  • 正方形上、左或下边框上的每个单元格都有 # 。
  • 每个其他单元格都有 . 。

您将获得 N \times N 网格。 每个细胞都有 # or . 。
网格描述为 N 字符串 S_1,S_2,\dots,S_N;的 j- 第一个字符 S_i 代表写在单元格上的字符 i从顶部开始的第行和 j左起第 列。

找到a的最大级别 C 可以通过从此网格中提取(连接的)正方形来获得。
如果没有从网格中提取的正方形形成 C,打印 0.

约束

  • N 是介于 3 和 300,包括在内。
  • S_i 是一个长度-N 字符串组成 # 和 ..

输入

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

N
S_1
S_2
\vdots
S_N

输出

将答案打印为整数。


示例输入 1

4
####
.#..
.###
#..#

示例输出 1

1

如果提取由以下组成的正方形 1-st 通过 3- 从顶部开始的第 行和 2-nd 通过 4第列,它形成一个 C 级别 1.
无法提取 C 级别 2 或此网格中的更大值。


示例输入 2

5
.####
.###.
####.
##..#
###.#

示例输出 2

0

无法提取 C 来自该网格。


示例输入 3

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

示例输出 3

3