LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?
Input
每组测试数据的第一行为n(2=

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N=55;
const int INF=0x3f3f3f3f;
struct node{
    int i,j;
    int d;
    node(int i,int j,int d):i(i),j(j),d(d){}
    friend bool operator < (node a,node b){
        return a.d>b.d;
    }
};
int dis[N][N];
int c[N][N];
int n;
bool vis[N][N];
long long dp[N][N];
int dir[4][2]={
  {
  0,-1},{-1,0},{
  0,1},{
  1,0}};
bool check(int i,int j){
    if(i<1 || i>n || j<1 || j>n || vis[i][j]){
        return false;
    }
    return true;
}
void bfs(){
    memset(vis,false,sizeof(vis));
    priority_queue<node> q;
    dis[n][n]=c[n][n];
    q.push(node(n,n,c[n][n]));
    vis[n][n]=1;
    while(!q.empty()){
        node tmp=q.top();
        int ti=tmp.i;
        int tj=tmp.j;
        int td=tmp.d;
        q.pop();
        for(int i=0;i<4;i++){
            if(check(ti+dir[i][0],tj+dir[i][1])){
                vis[ti+dir[i][0]][tj+dir[i][1]]=true;
                //printf("%d %d\n",ti+dir[i][0],tj+dir[i][1]);
                dis[ti+dir[i][0]][tj+dir[i][1]]=td+c[ti+dir[i][0]][tj+dir[i][1]];
                q.push(node(ti+dir[i][0],tj+dir[i][1],dis[ti+dir[i][0]][tj+dir[i][1]]));
                //printf("%d\n",dis[ti+dir[i][0]][tj+dir[i][1]]);
            }
        }
    }
    memset(vis,0,sizeof(vis));
}
long long solve(int i,int j){
    //printf("%d %d\n",i,j);
    if(dp[i][j]){
        return dp[i][j];
    }
    dp[i][j]=0;
    for(int k=0;k<4;k++){
        if(check(i+dir[k][0],j+dir[k][1]) && dis[i][j]>dis[i+dir[k][0]][j+dir[k][1]]){
            dp[i][j]+=solve(i+dir[k][0],j+dir[k][1]);
        }
    }
    return dp[i][j];
}
int main(void){
    //freopen("data.txt","r",stdin);
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&c[i][j]);
                dis[i][j]=INF;
                dp[i][j]=0;
            }
        }
        //bfs求出每个点到终点的最短路径
        bfs();
        // 只有满足b点到终点的最短路径小于a点到终点的最短路径
        // a-b这条路才可以走
        // for(int i=1;i<=n;i++){
   
        // for(int j=1;j<=n;j++){
   
        // printf("%d ",dis[i][j]);
        // }
        // printf("\n");
        // }
        dp[n][n]=1;
        long long ans=solve(1,1);
        printf("%lld\n",ans);
    }
    return 0;
}