Solution:
First of all, if kk is not an even number, there must be no answer.
Define map[i][j][d]map[i][j][d] (where 0≤d<40≤d<4) represents the side length of (i,j)(i,j) in four directions.
Define dp[p][i][j]dp[p][i][j] represents the minimum cost of starting from (i,j)(i,j), walking 2⋅p2⋅p to return to the (i,j)(i,j).
Sodp[p][i][j]=min0≤d<4dp[p−1][nexti][nextj]+map[i][j][d]dp[p][i][j]=min0≤d<4dp[p−1][nexti][nextj]+map[i][j][d]Where nextinexti and nextjnextjrepresents the coordinates of one step from (i,j)(i,j) with direction dd.
Code:
Submission #114076615 - Codeforces
Codeforces. Programming competitions and contests, programming community
