#28. 红十字

红十字

题目描述

通往藏宝库的通道打开了,走下一段长长的楼梯,钻过一条矮矮的地道,你和小可可终于来到了藏宝库的门前。随之而来的就是最后一个挑战,只要能打开宝库的门,里面的宝藏就是你们的了。

宝库的门依然是通过机关打开,这个门很奇怪,是一个正方形,被划分成许多大小一致的正方形的小方格,这些方格不是红色就是白色,猛看上去这些方格组成了许多红十字状的标志。根据藏宝图记载,只要找到门上最大的红十字,按下它中心的方格,宝库的门就能打开了。

红十字标志也是一个正方形,边长为 (2k+1)×(2k+1)(2k+1)\times (2k+1),其中 kk 为非负整数。它的四条边与门的边平行,而且恰由门上的 (2k+1)×(2k+1)(2k+1)\times (2k+1) 个小方格组成。这里,红十字标志是以白色为底色,红色为十字的颜色。假设用 1 表示红色,用 0 表示白色。对应到计算机处理的数据中,就是除了正中列与正中行全为 1 外,其余方格均为 0。以下是几种不同大小的标志:

1*1
1

3*3
010
111
010

5*5
00100
00100
11111
00100
00100

小可可被这个机关难到了,现在只有靠你了,请你帮助他在这个门上找到一个最大的红十字标志,输出它的边长即可。

输入格式

输入文件中第一行有一个整数 nn,表示门由 n×nn \times n 个方格组成。
以下 nn 行,每行 nn 个字符,每个字符都是 01。数据中不会出现全为 0 的情况。

输出格式

输出一个数,即最大的红十字标志的边长。

5
00011
01011
11100
01001
00010
3

数据规模与约定

对于 100%100\% 的数据,1n2×1031\le n\le 2\times 10^3