Description:
公式日本語
w*hのマスからなる崖がある。(2<=w<=30, 5<=h<=60)
各マスは1-9, S,T,Xのどれかである。
崖登りは、最下段のSのマスにどちらか片足を置くことから始める。
崖登りは、片足をあるマスに置きながら、もう片方の足を別のマスに伸ばす、といった移動の繰り返しで行われる。
途中、Xのマスに足を掛けることは出来ず、1-9のマスは、そのマスに足を掛けるのにそれだけの時間がかかる事を意味している。
最上段のTのマスに片足を掛ける事が出来れば、崖を登りきった事になる。
崖登りの途中、両足の位置は、左足、右足の座標を(lx, ly)、(rx, ry)として、 lx < rx && | lx - rx | + | ly - ry | <= 3 を満たさなくてはならない。
崖を登るのに最低どれだけの時間が必要か?
登るのが不可能な時は-1を出力せよ。
Answer:
支点とする足*x座標*y座標を状態として、ダイクストラを行えばよい。
Source: