ACPC2012Day2OL B.Grid
問題
r*cの2次元グリッド上の2点間マンハッタン距離で最小となる経路の数を返す。
ただし、グリッドは上下、左右がつながっており、右端は左端に移動、などができる。(トーラス)
考え方
2つの座標a,bについて、aを固定して考える。
bについて、グリッドの周りに8グリッド分拡張して考えると、上からいった場合、下からいった場合などのa,b間の距離が求められる。
a,bのx軸y軸の長さがわかったら、その経路の総数はdpで求められるので、拡張したbについて距離最小となっているところの経路数の合計を返す。