- 追加された行はこのように表示されます。
- 削除された行は
このように表示されます。
!!Problem D カーリング 2.0
MM-21星でもオリンピック以来カーリングが流行している. しかし, そのルールは地球のものとはすこし異なっており, マス目状の氷の盤上で石を一つだけ使って行われる. スタート位置からゴール位置まで石を到達させる移動回数の少なさを競うのである.
図 D-1 に盤面の例を示す. 盤上のマス目には障害物が配置されていることがある. 盤面には, スタートとゴールという特別なマスが一つずつあり, そこには障害物はない. (スタートとゴールが一致することはない.) 滑りはじめた石は障害物がないかぎりどこまでも進んでいくので, ゴールに到達させるには, 障害物を利用していったん石を止め, あらためて滑らせてやる必要もあろう.
図 D-1: 盤面の例 (S: スタート, G: ゴール)
石の動きは以下の規則に従う:
* ゲームの開始時に, 石はスタートで止まっている.
* 石の動きは x, y 方向に限る. ななめには動けない.
* 止まっている石は, 滑らせることによって動き出す. その時の方向は, すぐ次のマスに障害物がない方向ならどちらでもよい(図 D-2(a)).
* 動き出した石は, 次のいずれかが起こるまで, 同じ方向に動き続ける.
** 障害物にぶつかった場合(図 D-2(b), (c)).
*** 石は障害物の一つ手前のマスで止まる.
*** 障害物は消滅する.
** 盤外に出た場合.
*** 失敗でゲームは終わる.
** ゴールの上に来た場合.
*** そこで石は止まり, 成功でゲームは終わる.
* 1 回のゲーム中の滑らせる回数の最大は 10 である. この回数でゴールに石を到達させることができない場合, 失敗でゲームは終わる.
図 D-2: 石の動きの例
以上の条件のもとで, スタート位置にある石をゴール位置に到達させることができるか, できるなら最小何回滑らせればよいかを知りたい.
図 D-1 に示す初期配置では 4 回で石をスタート位置からゴール位置に動かすことができる. そのときの経路を図 D-3(a) に示す. なお, 石がゴールに到達した時点での盤面は図 D-3(b) のように変化している.
図 D-3: 図 D-1の解と終了時の盤面
!Input
入力はデータセットの並びである. 入力の終わりは, 一つの空白で区切られた二つのゼロからなる行で示される. データセット数が100を超えることはない.
各データセットは次のような形式をしている:
盤の幅(=w) 盤の高さ(=h)
盤面の1行目
...
盤面のh行目
盤の幅と高さは次の条件を満たす: 2 <= w <= 20, 1 <= h <= 20.
盤面の各行には, w個の数字が空白一つをはさんで並んでいる. その数字は対応するマス目の状態を示している.
0 何もないマス
1 障害物
2 スタート位置
3 ゴール位置
図 D-1 に対応するデータセットの記述は以下のようになる:
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
!Output
各データセットが指定する盤面について, スタート位置にある石をゴール位置に到達させるまでに滑らせる回数の最小値を, 十進の整数値でそれぞれ1行に出力せよ. そのような移動ができない場合には, -1 を出力せよ. 各出力行はこの数値以外の文字を含んではならない.
!Sample Input
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0
!Output for the Sample Input
1
4
-1
4
10
-1
!!解答例
再帰を使う。ほとんどOB会の解答例のまんま。
*[[2006dd1.c]]