← 返回题目列表

AtCoder · joi2009yo_d

D. 薄冰穿越

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

配点: 100 点

問題

在冬天寒冷的某一天,JOI太郎君决定打破广场上的薄冰游玩。广场是矩形的,东西方向有 m 块,南北方向有 n 块,也就是说被划分为m \times n 个区块。此外,有区块上有薄冰,有区块上没有薄冰。JOI太郎君按照以下规则,一边打破薄冰一边移动区块:

  • 从任何有薄冰的区块都可以开始打破薄冰。
  • 可以移动到东南方向任意一个相邻且尚未被打破的有薄冰的区块。
  • 必须打破移动到的区块的薄冰。

请编写一个程序,求 JOI 太郎君在打破薄冰的同时能够移动的最大区块数。不过,1 \leqq m \leqq 90,1 \leqq n \leqq 90 是。给定的输入数据中,移动方法 20 不超过万种。


入力

输入为 n+2 行。1 行是一个整数 m 上写着。2 行是一个整数 n 上写着。3 在 n+2 到第几行的每一行中,0 或 1 被空格隔开 m 个,表示每个区块是否有薄冰。从北边算起的 i 个区块,从西边算起的 j 个区块 (i, j) 记作(1 \leqq i \leqq n,1 \leqq j \leqq m),第 i+2 线 j 第几个值,如果区块 (i, j) 存在薄冰, 1 和分区 如果 (i, j) 处没有薄冰 0 变为。

出力

输出可移动的最大节数。 给出


入力例 1

3
3
1 1 0
1 0 1
1 1 0

出力例 1

5

入力例 1 最大值的移动方法示例 未给出


入力例 2

5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1

出力例 2

5

入力例 2 最大值的移动方法示例 未给出

入力例 2 最大值的移动方法示例