UOJ Logo

NOI.AC

1S 512MB

#1615. 十字架

Statistics

给一个$n imes m$的01矩阵,一个合法的十字架是指某个格子为1,并且上下左右四个方向同样长度延伸的所有格子也全为1,延伸的最大长度就是十字架的大小。求所有合法十字架中,最大的十字架的大小。

输入说明

第一行是$n$和$m$。分别表示01矩阵的长和宽。接下来$n$行,每行$m$个数字,表示矩阵上的数字,数字非0即1.

输出说明

一个数字,表示最大的十字架大小。

输入样例1

2 2
0 0 
0 0

输出样例1

0

输入样例2

2 2
1 1 
1 1

输出样例2

1

输入样例3

3 3
1 1 0
1 1 1
0 1 0

输出样例3

2

范围说明

  • 对于30%的数据有:$nleq 50, mleq 50$
  • 另有30%的数据有:$max(n, m) leq 1000, n imes mleq 10000$
  • 剩下40%的数据有:$nleq 1000, mleq 1000$