#joi2009yod. [joi2009yo_d]薄氷渡り
[joi2009yo_d]薄氷渡り
问题
在一个寒冷的冬日,JOI太郎决定去广场打碎薄冰玩耍。该广场是一个长方形区域,被分割成行列,即个小区域。其中,有一些区域有薄冰,有一些区域没有。JOI太郎根据以下规则移动并打碎薄冰:
- 可以从任何有薄冰的区域开始打碎。
- 可以向东、西、南、北四个方向之一移动到相邻的、尚未被打碎的有薄冰的区域。
- 必须打碎移动后到达的区域的薄冰。
请编写一个程序来求出JOI太郎在打碎薄冰的同时最多可以移动到多少个区域。输入数据满足,。在给定的输入数据中,移动方式不会超过20万种。
输入
输入共有行。第1行为整数。第2行为整数。接下来的第3行到第行的每行包含个用空格分隔的整数,表示每个区域是否有薄冰。第行的第个值表示第个区域是否有薄冰。其中,,。如果第个区域有薄冰,则对应的值为;如果没有薄冰,则对应的值为。
输出
输出可以移动到的区域的最大数量。
输入例子 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的无法达到最大移动方式示例