Amazing Mazes

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem B: 迷図と命ず

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

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

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

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

Input

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

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

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

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

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

Output

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

Sample Input

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

Output for the Sample Input

4
0
20

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2010-07-02
http://icpc2010.honiden.nii.ac.jp/