#include <stdio.h> #include <algorithm> #include <vector> #include <queue> #define INF 0x7fffffff using namespace std; typedef pair <int,int> ppair; typedef pair <int,ppair> pppair; priority_queue <pppair,vector<pppair>,greater<pppair> > Q; int N, A[2223][2223], D[2223][2223]; void input(void) { int i, j; scanf("%d",&N); for(i=1 ; i<=N ; i++) for(j=1 ; j<=N ; j++) { scanf("%d",&A[i][j]); D[i][j]=INF; } } void process(void) { int i, y, x, ty, tx; D[1][1]=0; Q.push(make_pair(0,make_pair(1,1))); while(!Q.empty()) { y=Q.top().second.first; x=Q.top().second.second; Q.pop(); ty=y; tx=x+1; if(ty>=1 && ty<=N && tx>=1 && tx<=N) { if(A[y][x]>A[ty][tx]) { if(D[ty][tx]>D[y][x]) { D[ty][tx]=D[y][x]; Q.push(make_pair(D[ty][tx],make_pair(ty,tx))); } } else if(D[ty][tx]>D[y][x]+A[ty][tx]-A[y][x]+1) { D[ty][tx]=D[y][x]+A[ty][tx]-A[y][x]+1; Q.push(make_pair(D[ty][tx],make_pair(ty,tx))); } } ty=y+1; tx=x; if(ty>=1 && ty<=N && tx>=1 && tx<=N) { if(A[y][x]>A[ty][tx]) { if(D[ty][tx]>D[y][x]) { D[ty][tx]=D[y][x]; Q.push(make_pair(D[ty][tx],make_pair(ty,tx))); } } else if(D[ty][tx]>D[y][x]+A[ty][tx]-A[y][x]+1) { D[ty][tx]=D[y][x]+A[ty][tx]-A[y][x]+1; Q.push(make_pair(D[ty][tx],make_pair(ty,tx))); } } } } void output(void) { printf("%d",D[N][N]); } int main(void) { input(); process(); output(); return 0; }