配点: 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 最大值的移动方法示例
