0145 - 迷図と命ず

日本語では「迷路」と呼ぶことが多い maze だが，英語と発音を似せて「迷図」と呼ぶ人もいる．迷図を通り抜けられないようでは，国内予選を通過するのも難しいかも!

この問題の迷図は，四角を縦横に並べた長方形の領域である．この領域は出入口を除いて壁で囲まれている．迷図の入口は長方形の上辺の最も左側で，つまり最上段の最左の四角の上辺は開いている．出口は同様に下辺の最も右側にある．

迷図の中では縦または横に隣り合う四角に行くことができる．しかし隣とは壁で隔てられていることがあり，その場合直接には行き来できない．

あなたの仕事は，入口から出口までの最短経路の長さを求めることである．最短経路が複数あることもあれば，ひとつもないこともあるのに注意されたい．

入力はそれぞれが迷図を表すひとつ以上のデータセットからなる．

データセットの最初の行には迷図の幅 w と高さ h を与えるふたつの整数値がこの順に入っている．

それに続く 2 × h - 1 行は，隣接する四角の間の壁の有無を示している．最初の行の先頭は空白で，その後には w - 1 個の 1 または 0 が空白ひとつで区切られて並んでいる．これらは一番上の行の横に隣り合う四角の間の壁の有無を示すものである．1 は壁があることを，0 はないことを意味する． 次の行の先頭には空白はなく，w 個の 1または 0 が空白ひとつを区切りに続く．これらは最初と次の行の縦に隣り合う四角の間の壁の有無を表す．整数 1/0 は壁の有/無を示す．引き続く行は交互に横と縦に隣り合う四角の間の壁の有無を同様に表す．

入力の終わりは二つのゼロを含む行で表される．

データセット数は100以下である．長方形領域の高さも幅も2以上30以下である．

各データセットについて，入口から出口までの最短経路長を表す整数ひとつを持つ行を出力せよ．ここでは経路の長さは通過する四角の数で表す．迷図を通り抜ける経路がない場合には，ゼロひとつを含む行を出力せよ．出力行にはこの数値以外の文字を含んではならない．

2 3
 1
0 1
 0
1 0
 1
9 4
 1 0 1 0 0 0 0 0
0 1 1 0 1 1 0 0 0
 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1
 0 0 0 1 0 0 1 1
0 0 0 0 1 1 0 0 0
 0 0 0 0 0 0 1 0
12 5
 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0
 0 0 1 0 0 1 0 1 0 0 0
0 0 0 1 1 0 1 1 0 1 1 0
 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0
0 0

4
0
20