Consider the following DP.

DP[i][j]=The number of moves to \((i, j)\)

Then, we can perform the DP with the following relatios:

$ \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} R

This methods needs a total of \(O(HW(H+W))\), which will receive a TLE.

To optimize the transitions by calculating cumulative sums while calculating DP for each direction: vertical, horizontal and diagonal. Specifically, let

\(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,\)

Then the answer can be found with the following pseudocode (the initial value, and boundaries and the walls on k are not considered):

\( \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] \)

Now the problem has been solved in an total \(O(HW)\) tine.

Note that, in this algorithms, in order to calculate \(DP[i][*]\), we don’t really need the elements other than \(DP[i-1][*]\), so we can store only “the current row” and “the previous row” , so that the answer can be found in a total of \(O(W)\) memory space.

Sample Code (C)