D - 薄氷渡り
Editorial
/ 
/ 
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 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 に対して，最大値を与えない移動方法の例