障害物のある座標を set で保持することで、ある座標に移動可能かどうかは \(O(\log M)\) で判定できます。

まずはより簡単な次の問題を考えます。

• 行えるワープは \((x+1,y),(x,y+1)\) の \(2\) 種類。その他は元の問題と同じ

この問題は
\({\rm dp}[n][x][y]=n\) 回のワープ後に \((x,y)\) にいるような移動経路の個数
とするDPにより \(O(N^3 \log M)\) 時間で問題を解くことができます。

元の問題に戻ります。この場合も、取りうる \((x,y)\) の値の種類が少ないことに着目し、DPテーブルを辞書などで保持することにより \(O(N^3(\log N+\log M))\) で解くことができます。高速な言語であればこの解法でACを得ることができます。

実装例(C++)

座標ではなく、移動回数の情報を持つ次のようなDPを行うと \(O(N^3\log M)\) で解くことができます。

\({\rm dp}[n][x][y][z]=n\) 回のワープのうち \(3\) 種類のワープをそれぞれ \(x,y,z\) 回行うような移動経路の個数

上記テーブルをそのまま配列で持つと空間計算量が \(O(N^4)\) になりますが、\(n=x+y+z\) であることから、\(z\) を状態として持つ必要はなく、\(O(N^3)\) になります。

以下の実装例では、\({\rm dp}[n-1],{\rm dp}[n]\) のみを保持することで空間計算量を \(O(N^2)\) にしています。
実装例(C++)
実装例(Python)