SRM509 div.2 1000 NumberLabyrinthDiv2

問題

TopCoder Statistics - Problem Statement
平面が与えられて、各格子には0〜9の数字もしくは空白(.)が与えられる。
数字の書いてある格子からは、4方向に数字の分だけジャンプして移動できる。0に来た場合はそれ以上移動できない。
スタート地点とゴール地点が与えられて、空白をK回まで書き換えてよいとした場合、移動回数の最小値を求めよ。
どうやってもゴールにたどり着けないときは-1を出力せよ。

解法

要はジャンプできる迷路。幅優先探索する。蟻本もそう言ってる。
問題は、空白の書き換えだけれども、空白に辿り着いたときは、1〜9まで全て書き換えてみれば良い。
書き換え回数の管理は、キューに(行, 列, 現在の書き換え回数)というペアを持たせておけば良い。
あと、一度書き換えたところを戻ることは考慮しなくてよい。なぜなら、戻ってゴールに辿り着ける場合は、必ずそれよりも少ない回数での辿りつき方があるからである。
計算量的にはpythonだと厳しかった(1.8sくらい)。

コード

感想

幅優先探索までは思いついたけど、書き換えをどうするかが分からなかった。
python2のcollections.dequeとQueue.Queue、heapqとQueue.PriorityQueueってそれぞれどっちが速いのだろうか...