題目描述:
Euphemia 到一個 N*N 的藥草田里采藥,她從左上角的格子田(第一行,第
一列)出發,要到達右下角(第 N 行,第 N 列)的格子田,每次她可以走到與
當前格子有邊相鄰的格子去,但她不會走已經走過的格子,而且出于對美的要求,
她走過的路徑是關于 左下-右上 對角線對稱的。由于地勢不同,在每個格子田
采藥都會有一個疲勞度 Tij,Euphemia 想知道:有多少條合法路徑,可以使得她
采藥的疲勞度最小。
輸入格式:
多組數據。
每組數據第一行一個整數 N,接下來 N 行,每行 N 個非零數字(1,2,3...9 中
一個),表示格子田的疲勞度。
當 N=0,輸入結束。
輸出格式:
對于每組數據,輸出一個整數表示答案,答案%1000000009。
樣例輸入:
2
1
1
3
1
1
2
0
1
1
1 1
1 1
1 1
樣例輸出:
2
3數據范圍與限制:
對于 20%的數據滿足 N<=5。
對于另外 20%的數據滿足 N<=40。
對于 100%的數據滿足 N<=100,不超過 50 組數據。

首先我們可以把線的兩邊對折，這樣就變成了半個矩陣，同時問題就轉化成了從左上角到折線的位置的最短路徑的條數有多少。
然后，我們可以用SPFA求單源最短路，這樣起點到每個點的最短路就都有了。之后為了能夠算出路徑的條數，我們可以從起點開始，每次取隊中d[]的值最小的點出隊，然后按最短路徑的走向向周圍的點拓展，并將拓展成功的點入隊。
最后，統計折線上的最短路的最小值，并把所有符合要求的路徑的條數相加即可

其實SPFA和拓展求出路徑條數的過程可以在一個SPFA內完成

有一個坑點就是如果一個點不在對角線且未在隊列就說明：

1.這個點的未走過

2.這個點已出隊，意味著對于它旁邊的點，他已經加上了該點原來的路徑數

如果不清零，接下來的過程會再算一遍，產生重復

意思就是如果(x+y<n+1&&vis[x][y]==0) 路徑數[x][y]=0

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 typedef long long lol; 8 struct Node 9 { 10 int x,y; 11 }; 12 lol Mod=1000000009; 13 const int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1}; 14 lol dist[201][201],d[101][101],as,ans; 15 int n,a[201][201]; 16 bool vis[101][101]; 17 void SPFA() 18 {int i; 19 queue<Node>Q; 20 memset(dist,127/3,sizeof(dist)); 21 memset(vis,0,sizeof(vis)); 22 memset(d,0,sizeof(d)); 23 dist[1][1]=0; 24 d[1][1]=1; 25 Q.push((Node){1,1}); 26 while (Q.empty()==0) 27 { 28 Node u=Q.front(); 29 Q.pop(); 30 vis[u.x][u.y]=0; 31 if (u.x+u.y==n+1) continue; 32 for (i=1;i<=4;i++) 33 { 34 int x=u.x+dx[i],y=u.y+dy[i]; 35 if (x&&y&&x<=n&&y<=n&&y<=n-x+1&&dist[x][y]>=dist[u.x][u.y]+a[u.x][u.y]+a[n-u.y+1][n-u.x+1]) 36 { 37 if (dist[x][y]>dist[u.x][u.y]+a[u.x][u.y]+a[n-u.y+1][n-u.x+1]) 38 { 39 dist[x][y]=dist[u.x][u.y]+a[u.x][u.y]+a[n-u.y+1][n-u.x+1]; 40 d[x][y]=d[u.x][u.y]%Mod; 41 if (x+y<n+1&&vis[x][y]==0) 42 { 43 Q.push((Node){x,y}); 44 vis[x][y]=1; 45 } 46 } 47 else 48 if (dist[x][y]==dist[u.x][u.y]+a[u.x][u.y]+a[n-u.y+1][n-u.x+1]) 49 { 50 if(vis[x][y]==0&&x+y<n+1)d[x][y]=0; 51 d[x][y]+=d[u.x][u.y]; 52 d[x][y]%=Mod; 53 if (x+y<n+1&&vis[x][y]==0) 54 { 55 Q.push((Node){x,y}); 56 vis[x][y]=1; 57 } 58 } 59 } 60 } 61 } 62 } 63 int main() 64 {int i,j; 65 while (cin>>n&&n) 66 { 67 for (i=1;i<=n;i++) 68 { 69 for (j=1;j<=n;j++) 70 { 71 scanf("%d",&a[i][j]); 72 } 73 } 74 SPFA(); 75 as=2e9;ans=0; 76 for (i=1;i<=n;i++) 77 as=min(as,dist[i][n-i+1]+a[i][n-i+1]); 78 for (i=1;i<=n;i++) 79 if (as==dist[i][n-i+1]+a[i][n-i+1]) 80 ans+=d[i][n-i+1],ans%=Mod; 81 82 cout<<ans<<endl; 83 } 84 }

?

轉載于:https://www.cnblogs.com/Y-E-T-I/p/7569279.html

總結

以上是生活随笔為你收集整理的路径数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。