← 返回题目列表

Codeforces · 135/D

D. 循环

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

小Petya非常喜欢由字符“0”和“1”组成的长方形桌子。最近他收到了一张这样的桌子作为他母亲送给他的礼物。该表包含 n 行和 m 列。行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。佩蒂亚立即决定不惜一切代价找到最长的冷却周期。

循环是成对不同单元的序列,其中每两个连续单元具有公共边;此外,第一个单元与最后一个单元有公共边。如果一个循环同时满足以下所有条件,则称为冷循环:

- 循环完全由包含“1”的单元格组成。
- 属于该循环的每个单元格与属于该循环的其他两个单元格具有公共边。
- 表中包含“1”的每个单元格要么属于循环,要么位于循环之外(请参见下面的定义)。

为了正式定义“外部”的概念,让我们在平面上画一个循环。令循环(i,j)的每个单元格(i为行号,j为列号)对应于坐标平面上的点(i,j)。让一条直线段连接对应于属于循环并共享一条边的单元的每对点。这样,我们将得到一条没有自相交和自接触的闭合折线。折线将平面分为两个相连的部分:无限区域的部分和有限区域的部分。如果单元格(r,c)不属于循环且坐标为(r,c)的平面上的对应点位于无穷大区域内,则认为单元格(r,c)位于循环之外。

帮助 Petya 找出表中最长冷却周期的长度。周期长度定义为属于该周期的细胞数量。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000) — 分别是表中的行数和列数。以下 n 行每行包含 m 个字符。每个字符可以是“0”或“1”。

输出

打印单个数字 — 表中最长冷却周期的长度。如果这样的循环不存在,则打印 0。

示例

输入 #1

3 3
111
101
111

输出 #1

8

输入 #2

5 5
01010
10101
01010
10101
01010

输出 #2

0

输入 #3

7 7
1111111
1000101
1000101
1000101
1000111
1000001
1111111

输出 #3

24

输入#4

5 5
11111
10001
10101
10001
11111

输出#4

0

注意

在第一个示例中只有一个周期,这很酷。

在第二个示例中根本没有循环。

在第三个示例中,有两个冷却循环:它们的长度为 12 和 24。

在第四个示例中也只有一个周期,但这并不酷,因为该周期内有一个包含“1”的单元格。