ACPC2012Day2OL B.Grid

問題

r*cの2次元グリッド上の2点間マンハッタン距離で最小となる経路の数を返す。
ただし、グリッドは上下、左右がつながっており、右端は左端に移動、などができる。(トーラス)

考え方

2つの座標a,bについて、aを固定して考える。
bについて、グリッドの周りに8グリッド分拡張して考えると、上からいった場合、下からいった場合などのa,b間の距離が求められる。
a,bのx軸y軸の長さがわかったら、その経路の総数はdpで求められるので、拡張したbについて距離最小となっているところの経路数の合計を返す。