7-3 minimum toll

7-3 Minimum tolls

A businessman walked through a N×N A grid of squares , Go to a very important business activity .

He wants to enter from the upper left corner of the grid , Lower right corner out .

Every time you cross the middle 1 A small square , All costs. 1 Unit time .

Businessmen must be in (2N−1) A unit of time goes through .

And when passing through each small square in the middle , All need to pay a certain fee .

The merchant expects to cross out with the least cost within the specified time .

How much does it cost at least ？

Be careful ： You can't cross small squares diagonally （ namely , It can only move up, down, left and right, and cannot leave the grid ）.

Input format
The first line is an integer , Represents the width of the square N.

Back N That's ok , Each row N No more than one. 100 The positive integer , For the cost of each small square on the grid .

Output format
Output an integer , Indicates the minimum cost required .

Data range
1≤N≤100

sample input ：

5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33

sample output ：

109

Sample explanation
In the example , The minimum value is 109=1+2+5+7+9+12+19+21+33.
Code ：

#include<iostream>
using namespace std;
int main()
{
    
    int n,i,j,a[102][102];
    cin>>n;
    for (i=0;i<102;i++)
        for (j=0;j<102;j++)
            a[i][j]=9990;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            cin>>a[i][j];
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        {
    
            if (i==1&&j==1)
                continue;
            else
            {
    
                if (a[i][j]+a[i][j-1]>a[i][j]+a[i-1][j])
                a[i][j]=a[i][j]+a[i-1][j];
                if(a[i][j]+a[i][j-1]<=a[i][j]+a[i-1][j])
                a[i][j]=a[i][j]+a[i][j-1];
            }
        }
    cout<<a[n][n]<<endl;
    return 0;
}

202206260904 Japan