Problem Description
LL最近沉迷於AC不能自拔，每天寢室、機房兩點一線。由於長時間坐在電腦邊，缺乏運動。他決定充分利用每次從寢室到機房的時間，在校園裡散散步。整個HDU校園呈方形布局，可劃分為n*n個小方格，代表各個區域。例如LL居住的18號宿捨位於校園的西北角，即方格(1,1)代表的地方，而機房所在的第三實驗樓處於東南端的(n,n)。因有多條路線可以選擇，LL希望每次的散步路線都不一樣。另外，他考慮從A區域到B區域僅當存在一條從B到機房的路線比任何一條從A到機房的路線更近(否則可能永遠都到不了機房了…)。現在他想知道的是，所有滿足要求的路線一共有多少條。你能告訴他嗎?
Output
針對每組測試數據，輸出總的路線數(小於2^63)。
Sample Input
3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1
Sample Output
1
6
剛開始竟然把題意搞錯了，"想把每個方格映射為一個點，一個格子到下一個格子的距離為當前格子的時間"。。
後來一想，這樣，a->b和 b->a的距離就不一樣了。有點想當然了。。。
正確的方法是：直接把格子作為一個點，求（n,n）點到各個點的最短路，然後，按照條件搜索就行了。
#include
#include
#include
#include
#include
using namespace std;
#define LL __int64
#define N 55
const int inf=(int)1e9;
int a[N][N],n;
LL num[N][N]; //存儲每個格子的可行路線數
int dis[N][N],mark[N][N]; //記錄每個方格到終點的最短時間
int dir[4][2]={0,1,0,-1,-1,0,1,0};
struct node
{
int x,y,t;
};
void inti()
{
int i,j;
for(i=0;iq;
inti();
node cur,next;
x=cur.x=s/n;
y=cur.y=s%n;
cur.t=a[x][y];
dis[x][y]=cur.t;
q.push(cur);
while(!q.empty())
{
cur=q.front();
q.pop();
x=cur.x;
y=cur.y;
mark[x][y]=0;
for(i=0;i<4;i++)
{
next.x=di=cur.x+dir[i][0];
next.y=dj=cur.y+dir[i][1];
if(di<0||di>=n||dj<0||dj>=n)
continue;
int tmp=dis[x][y]+a[di][dj];
if(dis[di][dj]>tmp)
{
next.t=dis[di][dj]=tmp;
if(!mark[di][dj])
{
mark[di][dj]=1;
q.push(next);
// printf("%d %d %d\n",next.x,next.y,next.t);
}
}
}
}
}
LL dfs(int x,int y)
{
if(num[x][y]!=-1)
return num[x][y];
int i,di,dj;
LL tmp=0;
for(i=0;i<4;i++)
{
di=dir[i][0]+x;
dj=dir[i][1]+y;
if(di<0||di>=n||dj<0||dj>=n)
continue;
if(dis[x][y]>dis[di][dj])
tmp+=dfs(di,dj);
}
return num[x][y]=tmp;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=-1)
{
for(i=0;i
