Problem Description
LL最近沉迷於AC不能自拔,每天寢室、機房兩點一線。由於長時間坐在電腦邊,缺乏運動。他決定充分利用每次從寢室到機房的時間,在校園裡散散步。整個HDU校園呈方形布局,可劃分為n*n個小方格,代表各個區域。例如LL居住的18號宿捨位於校園的西北角,即方格(1,1)代表的地方,而機房所在的第三實驗樓處於東南端的(n,n)。因有多條路線可以選擇,LL希望每次的散步路線都不一樣。另外,他考慮從A區域到B區域僅當存在一條從B到機房的路線比任何一條從A到機房的路線更近(否則可能永遠都到不了機房了…)。現在他想知道的是,所有滿足要求的路線一共有多少條。你能告訴他嗎?
Input
每組測試數據的第一行為n(2=<n<=50),接下來的n行每行有n個數,代表經過每個區域所花的時間t(0<t<=50)(由於寢室與機房均在三樓,故起點與終點也得費時)。
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
#include<stdio.h> #include<iostream> #include<queue> using namespace std; typedef struct nn { int dist,x,y; friend bool operator <(nn n1,nn n2) { return n1.dist>n2.dist; } }node; int map[55][55],N[55][55],n; __int64 dp[55][55]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; void BFS()//求每一點到終點的最小距離,從終點出發 { priority_queue<node> Q; node q,p; int i,tx,ty; q.x=q.y=n; q.dist=map[n][n]; Q.push(q); N[n][n]=map[n][n]; while(!Q.empty()) { q=Q.top(); Q.pop(); for(i=0;i<4;i++) { tx=q.x+dir[i][1];ty=q.y+dir[i][0]; if(tx>0&&tx<=n&&ty>0&&ty<=n) if(N[ty][tx]==-1||N[ty][tx]>N[q.y][q.x]+map[ty][tx])//當前點還沒有用過或是用過了又不是最小距離,才執行 { p.x=tx;p.y=ty; p.dist=N[q.y][q.x]+map[ty][tx]; N[ty][tx]=p.dist; Q.push(p); } } }//printf("%d",N[1][1]); } __int64 DFS(int x,int y)//記憶化搜索,每點到終點滿足條件有多少種走法 { int e,tx,ty; if(dp[y][x]>0)//當前的點己經走過了,直接反回當前的點有多少種走法 return dp[y][x]; if(x==n&&y==n) return 1; for(e=0;e<4;e++)//當前點所走的范圍,所以會把它所有范圍的點到終點的走法全加起來 { tx=x+dir[e][1];ty=y+dir[e][0]; if(ty>0&&ty<=n&&tx>0&&tx<=n) if(N[y][x]>N[ty][tx])//當前的點到終點距離要大於它將要走的點到終點的距離,有多少種走法 { dp[y][x]+=DFS(tx,ty); } } return dp[y][x];//當前點的范圍走完時,反回給它所在其他點的范圍 } int main() { int i,j; __int64 k; while(scanf("%d",&n)>0) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&map[i][j]); N[i][j]=-1;dp[i][j]=0; } BFS(); /*for(i=1;i<=n;i++) {printf("\n"); for(j=1;j<=n;j++) printf("%d ",N[i][j]); }*/ k=DFS(1,1); printf("%I64d\n",k); } } #include<stdio.h> #include<iostream> #include<queue> using namespace std; typedef struct nn { int dist,x,y; friend bool operator <(nn n1,nn n2) { return n1.dist>n2.dist; } }node; int map[55][55],N[55][55],n; __int64 dp[55][55]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; void BFS()//求每一點到終點的最小距離,從終點出發 { priority_queue<node> Q; node q,p; int i,tx,ty; q.x=q.y=n; q.dist=map[n][n]; Q.push(q); N[n][n]=map[n][n]; while(!Q.empty()) { q=Q.top(); Q.pop(); for(i=0;i<4;i++) { tx=q.x+dir[i][1];ty=q.y+dir[i][0]; if(tx>0&&tx<=n&&ty>0&&ty<=n) if(N[ty][tx]==-1||N[ty][tx]>N[q.y][q.x]+map[ty][tx])//當前點還沒有用過或是用過了又不是最小距離,才執行 { p.x=tx;p.y=ty; p.dist=N[q.y][q.x]+map[ty][tx]; N[ty][tx]=p.dist; Q.push(p); } } }//printf("%d",N[1][1]); } __int64 DFS(int x,int y)//記憶化搜索,每點到終點滿足條件有多少種走法 { int e,tx,ty; if(dp[y][x]>0)//當前的點己經走過了,直接反回當前的點有多少種走法 return dp[y][x]; if(x==n&&y==n) return 1; for(e=0;e<4;e++)//當前點所走的范圍,所以會把它所有范圍的點到終點的走法全加起來 { tx=x+dir[e][1];ty=y+dir[e][0]; if(ty>0&&ty<=n&&tx>0&&tx<=n) if(N[y][x]>N[ty][tx])//當前的點到終點距離要大於它將要走的點到終點的距離,有多少種走法 { dp[y][x]+=DFS(tx,ty); } } return dp[y][x];//當前點的范圍走完時,反回給它所在其他點的范圍 } int main() { int i,j; __int64 k; while(scanf("%d",&n)>0) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&map[i][j]); N[i][j]=-1;dp[i][j]=0; } BFS(); /*for(i=1;i<=n;i++) {printf("\n"); for(j=1;j<=n;j++) printf("%d ",N[i][j]); }*/ k=DFS(1,1); printf("%I64d\n",k); } }