次のようなDPを考えます。

DP[i][j]=マス(i,j)まで移動する方法の数

このとき、

\[ \begin{aligned} DP[i][j]&=&DP[i][j-1]+DP[i][j-2]+\ldots\\ &+& DP[i-1][j]+DP[i-2][j]+\ldots\\ &+& DP[i-1][j-1]+dp[i-2][j-2]+\ldots \end{aligned} \]

としてDPを行うことができます。この方法は時間計算量\(O(HW(H+W))\)であり、TLEとなります。

縦横ななめそれぞれの方向について、累積和を求めながらDPを行うことで遷移を高速化することができます。具体的には

\(X[i][j]=DP[i][j-1]+DP[i][j-2]+\ldots\\ Y[i][j]=DP[i-1][j]+DP[i-2][j]+\ldots\\ Z[i][j]=DP[i-1][j-1]+dp[i-2][j-2]+\ldots\)

とすると、次のような擬似コードにより求めることができます（初期値や境界、壁のマスに対する処理を省略しています）。

\( \text{for } i \text{ in } 1..H\\ \ \ \ \text{for }j \text{ in } 1..W\\ \ \ \ \ \ \ X[i][j] \leftarrow X[i][j-1]+DP[i][j-1]\\ \ \ \ \ \ \ Y[i][j] \leftarrow Y[i-1][j]+DP[i-1][j]\\ \ \ \ \ \ \ Z[i][j] \leftarrow Z[i-1][j-1]+DP[i-1][j-1]\\ \ \ \ \ \ \ DP[i][j]\leftarrow X[i][j]+Y[i][j]+Z[i][j] \)

これで時間計算量 \(O(HW)\) で解けるようになりました。

なお、このアルゴリズムにおいて、\(DP[i][*]\) などを計算するためには、\(DP[i-1][*]\) などしか必要がないことから、「今の行」「前の行」の2行分だけのデータを持って計算を行うことで、空間計算量\(O(W)\) で求めることができます。

回答例(C)