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:
Submission #114076615 - Codeforces
Codeforces. Programming competitions and contests, programming community
