#include <cstdio>

 #include <queue>

 #include <cstring>

 #include <algorithm>

 #define maxn 100

 #define ll __int64

 using namespace std;

 const int inf=<<;

 int g[maxn][maxn];

 bool vis[maxn][maxn];

 ll dis[maxn][maxn];

 ll dp[maxn][maxn];

 int n;

 int dir[][]={{,},{,-},{,},{-,}};

 struct node

 {

     int x,y,w;

     bool friend operator <(node a,node b)

     {

         return a.w>b.w;

     }

 }st1,st;

 void dijstra(int x,int y)

 {

     memset(vis,false,sizeof(vis));

     for(int i=; i<=n; i++)

     {

         for(int j=; j<=n; j++)

         {

             dis[i][j]=inf;

         }

     }

     priority_queue<node>q;

     st.x=x;

     st.y=y;

     st.w=g[x][y];

     dis[x][y]=g[x][y];

     q.push(st);

     while(!q.empty())

     {

         st1=q.top();q.pop();

         if(vis[st1.x][st1.y]) continue;

         vis[st1.x][st1.y]=true;

         for(int i=; i<; i++)

         {

             int xx=st1.x+dir[i][];

             int yy=st1.y+dir[i][];

             if(xx>=&&xx<n&&yy>=&&yy<n&&!vis[xx][yy])

             {

                 if(dis[st1.x][st1.y]+g[xx][yy]<dis[xx][yy])

                 {

                     dis[xx][yy]=dis[st1.x][st1.y]+g[xx][yy];

                     st.x=xx;

                     st.y=yy;

                     st.w=dis[xx][yy];

                     q.push(st);

                 }

             }

         }

     }

 }

 ll dfs(int x,int y)

 {

     if(dp[x][y]) return dp[x][y];

     for(int i=; i<; i++)

     {

         int x1=x+dir[i][];

         int y1=y+dir[i][];

         if(x1>=&&x1<n&&y1>=&&y1<n&&dis[x1][y1]<dis[x][y])

         dp[x][y]+=dfs(x1,y1);

     }

     return dp[x][y];

 }

 int main()

 {

      while(scanf("%d",&n)!=EOF)

      {

          memset(g,,sizeof(g));

          for(int i=; i<n; i++)

          {

              for(int j=; j<n; j++)

              {

                  scanf("%d",&g[i][j]);

              }

          }

          dijstra(n-,n-);

          memset(dp,,sizeof(dp));

          dp[n-][n-]=;

          printf("%I64d\n",dfs(,));

      }

      return ;

 }