Crossing Black Ice

Time Limit : 1 sec, Memory Limit : 65536 KB

薄氷渡り

問題

冬の寒いある日,JOI太郎君は広場にはった薄氷を割って遊ぶことにした.広場は長方形で,東西方向に m 個,南北方向に n 個,つまり, m × n の区画に区切られている.また,薄氷が有る区画と無い区画がある. JOI太郎君は,次のルールにしたがって,薄氷を割りながら区画を移動することにした.

  • 薄氷があるどの区画からも薄氷を割り始めることができる.
  • 東西南北のいずれかの方向に隣接し, まだ割られていない薄氷のある区画に移動できる.
  • 移動した先の区画の薄氷をかならず割る.

JOI太郎君が薄氷を割りながら移動できる区画数の最大値を求めるプログラムを作成せよ.ただし, 1 ≤ m ≤ 90,1 ≤ n ≤ 90 である.与えられる入力データでは,移動方法は20万通りを超えない.

入力

入力は複数のデータセットからなる.各データセットは以下の形式で与えられる.

入力はn+2行ある. 1 行目には整数 m が書かれている. 2 行目には整数 n が書かれている. 3 行目から n+2 行目までの各行には、0 もしくは 1 が, 空白で区切られて m 個書かれており,各区画に薄氷があるか否かを表している.北から i 番目,西からj番目の区画を (i,j) と記述することにすると (1 ≤ i ≤ n, 1 ≤ j ≤ m),第 i+2 行目の j 番目の値は,区画 (i,j) に薄氷が存在する場合は 1 となり,区画 (i,j) に薄氷が存在しない場合は 0 となる.

m, n がともに 0 のとき入力の終了を示す. データセットの数は 5 を超えない.

出力

データセットごとに, 移動できる区画数の最大値を1行に出力せよ.

入出力例

入力例

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

出力例

5
5

1つ目の入力例に対して,最大値を与える移動方法の例  
入力例1の場合

2つ目の入力例に対して,最大値を与える移動方法の例
入力例2の場合

2つ目の入力例に対して,最大値を与えない移動方法の例
入力例2の場合1 入力例2の場合2 入力例2の場合3 入力例2の場合4 入力例2の場合5

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Source: 8th Japanese Olympiad in Informatics, Preliminary Round , 2008-12-14
http://www.ioi-jp.org/