Minimum Cost Path on a Grid with Custom Edge Weights
Given an N x M grid, where each cell (i, j) contains a positive integer value V[i][j]. You start at cell (0, 0) and want to reach cell (N-1, M-1). You can move from a cell (r, c) to an adjacent cell (nr, nc) (up, down, left, or right). The cost of moving from (r, c) to (nr, nc) is defined as the value in the destination cell, V[nr][nc], if V[nr][nc] is greater than or equal to V[r][c]. If V[nr][nc] is strictly less than V[r][c], the cost is V[nr][nc] + (V[r][c] - V[nr][nc] + 1)^2. Calculate the minimum total cost to travel from (0, 0) to (N-1, M-1). The cost of the starting cell (0,0) is not included in the total cost.
Input
The first line contains two integers N and M (1 <= N, M <= 400). The next N lines each contain M integers, representing the grid values V[i][j] (1 <= V[i][j] <= 10^9).
Output
Print a single integer: the minimum cost to reach cell (N-1, M-1) from (0, 0).
Constraints
1 <= N, M <= 400, N * M <= 160000. 1 <= V[i][j] <= 10^9.
Example 1
2 2 1 3 2 4
6
Path: (0,0) -> (0,1) -> (1,1). Cost = 3 (to (0,1)) + 4 (to (1,1)) = 7. Or (0,0) -> (1,0) -> (1,1). Cost = 2 (to (1,0)) + 4 (to (1,1)) = 6. Minimum is 6.
Example 2
3 3 10 2 1 3 10 5 4 6 10
87
The minimum cost path is 18. A possible path yielding this cost is (0,0)[10] -> (0,1)[2] -> (0,2)[1] -> (1,2)[5] -> (2,2)[10]. However, the direct calculation of this path's cost is not 18, suggesting a more complex optimal path. For example, moving from (0,0)[10] to (0,1)[2] incurs a penalty: 2 + (
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
2 2 1 3 2 4
3 3 10 2 1 3 10 5 4 6 10