Baekjoon #11909

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N; cin >> N;
    vector<vector<int>> V(N, vector<int>(N));
    vector<vector<int>> DP(N, vector<int>(N, INF));
    DP[0][0]=0;
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            cin >> V[i][j];
            if(j > 0){
                int d = max(0, V[i][j] - V[i][j-1] + 1);
                DP[i][j]=min(DP[i][j], DP[i][j-1] + d);
            }
            if(i > 0){
                int d = max(0, V[i][j] - V[i-1][j] + 1);
                DP[i][j] = min(DP[i][j], DP[i-1][j] + d);
            }
        }
    }
    cout << DP[N-1][N-1];

    return 0;
}

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

inf = float('inf')
n = int(input())
prison = [list(map(int, input().split())) for _ in range(n)]
dp = [[inf] * n for _ in range(n)]
dp[0][0] = 0
dirx = [1, 0]
diry = [0, 1]

q = deque()
q.append((0, 0))
while q:
    x, y = q.popleft()
    for dx, dy in zip(dirx, diry):
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < n:
            cost = prison[nx][ny] - prison[x][y] + 1
            if cost < 1:
                cost = 0
            if dp[nx][ny] > dp[x][y] + cost:
                q.append((nx, ny))
                dp[nx][ny] = dp[x][y] + cost

print(dp[n - 1][n - 1])