プログラミングのお題スレ Part17

308 ：デフォルトの名無しさん：2020/04/27(月) 22:50:44.47 ID:pfA6eg61.net

お題：ワープ付き迷路
始点(S)、終点 (G)、通路(.)、ワープ(0-9)、壁(#)で構成される大きさH×Wの迷路を考える
プレイヤーは、隣接する壁以外のマスにコスト1で移動することができる
ワープマスに入った場合、プレイヤーは対となるワープマスにコスト0で強制的に移動する
迷路中に存在する0-9の個数は、各数字について0個または2個である

始点から終点に移動するときの最小コストを求めよ
ただし、終点に到達できない場合は"impossible"と出力せよ

4 6
1#S...
....#.
#####.
1..G..
=> 7 (ワープを使わずに右に進むとコストは8)

3 3
S1G
###
1##
=> impossible (ワープ先で身動きが取れなくなる)

1 22
S01234567890123498765G
=> 5 (S→0→9→4→5→G)