Codeforces Round #718 Explorer Space - DP

Solution:

First of all, if $k$ is not an even number, there must be no answer.

Define $map[i][j][d]$ (where $0 \leq d <4$) represents the side length of $(i,j)$ in four directions.

Define $dp[p][i][j]$ represents the minimum cost of starting from $(i,j)$, walking $2\cdot p$ to return to the $(i,j)$.

So$$dp[p][i][j]=\min\limits_{0 \leq d  < 4} dp[p-1][next_i][next_j]+map[i][j][d]$$Where $next_i$ and $next_j$represents the coordinates of one step from $(i,j)$ with direction $d$.

Code: