Contest Duration: - (local time) (100 minutes) Back to Home

## E - Queen on Grid Editorial by evima

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)

posted:
last update: