Problem solving path number + algorithm reverberation dp
Description
Background of topic
Euphemia\texttt{Euphemia}Euphemia to a N × NN\times NN × N herb field, she starts from the lattice field (the first row, the first column) in the upper left corner, and reaches the lower right corner (the NNN row, the NNN row Column), each time she can go to the grid adjacent to the current grid, but she will not go to the grid she has already passed, and because of the demand for beauty, the path she has gone is about the diagonal symmetry of the lower left and upper right. Due to the different terrain, there will be a fatigue degree Ti, JT {I, J} Ti, J, Euphemia\texttt{Euphemia}Euphemia would like to know how many legal paths can make her least fatigue degree of drug collection.
Input format:
Multiple sets of test data.
The first line of each group of data is an integer NNN, and the next NNN lines are NNN non-zero numbers (one of 1,2,3... 91,2,3... 91,2,3... 9), indicating the fatigue degree of lattice field.
When N=0N=0N=0, the input ends.
Output format:
For each group of data, output an integer to represent the answer, answer% 100000009 \% 100000009% 100000009.
Sample input:
2 1 1 1 1 3 1 1 1 1 1 1 2 1 1 0
Sample output:
2 3
Data range:
For 20% 20 \% 20% data, n ≤ 5N\le5N ≤ 5.
For the other 20% 20 \% 20% data, N ≤ 40N\le40N ≤ 40 is met.
For 100% 100 \% 100% data, n ≤ 100N\le100N ≤ 100, no more than 505050 groups of data.
Introduction
It's easy to score:
If you use dfs\texttt{dfs}dfs to brutally enumerate paths, you can get 20 points \ color {ා f34c05} \ texttt {20 points} 20 points.
If you use the wrong way of thinking Θ (n2)\Theta(n^2) Θ (n2) to dp\texttt{dp}dp, you can also get 60 points \ color {ffcc00} \ texttt {60} 60 points (only go to the lower right corner, do not look back).
Solution
Find the path minimum weight first
First of all, since you want to walk from the lower left corner to the lower right corner and the route is symmetrical according to the diagonal from the lower left to the upper right, the weight relative to each lattice is:
vali,j={Ti,j+TN−j+1,N−i+1(i+j<N+1)Ti,j(i+j==N+1) val_{i,j}= \begin{cases} T_{i,j}+T_{N-j+1,N-i+1}(i+j<N+1)\\ T_{i,j}(i+j==N+1) \end{cases} vali,j={Ti,j+TN−j+1,N−i+1(i+j<N+1)Ti,j(i+j==N+1)
Then, for the lattice with I + J > N + 1I + J > N + 1I + J > N + 1, it is unnecessary to consider the minimum weight path from the upper left corner of (1,1) (1,1) to the lattice with i+j==N+1i+j==N+1i+j==N+1.
The algorithm to find the shortest path is: echo dp\texttt{dp}dp.
Because the algorithm is the brainchild of Ben konjaku in the exam room, so he gave it a strange name.
Because the topic does not always say that it can only go down left, the following disgusting data may appear:
10 1 1 1 1 1 9 9 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 9 9 1 1 1 1 9 9 9 9 9 9 9 9 9 1 9 1 1 1 9 9 9 9 9 1 9 1 9 1 9 9 9 9 9 1 1 1 9 1 9 9 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 9 9 1 0
At this time, the minimum weight path should be along 111 in the figure. If you use normal dp\texttt{dp}dp, it will be difficult to find a proper recursive order.
However, since it only has nnn turns at most, it can be considered as follows:
Repeat nnn times
From the top left corner to the axis of symmetry, dp\texttt{dp}dp.
Reverse order dp\texttt{dp}dp from the axis of symmetry to the upper left corner.
This ensures that any path can be covered. \ texttt {DP} DP.
Code:
//... bool zxf(){//Top left to axis of symmetry bool res=0; for(int i=3;i<=n+1;i++) for(int x=1;x<i;x++){ int y=i-x; if(min(f[x][y-1],f[x-1][y])+val(x,y)<f[x][y]) f[x][y]=min(f[x][y-1],f[x-1][y])+val(x,y),res=1; } return res; } bool fxf(){//Axis of symmetry to top left bool res=0; for(int i=n;i>=2;i--) for(int x=1;x<i;x++){ int y=i-x; if(min(f[x][y+1],f[x+1][y])+val(x,y)<f[x][y]) f[x][y]=min(f[x][y+1],f[x+1][y])+val(x,y),res=1; } return res; } //... void dp(){ //... memset(f,0x3f,sizeof f); f[1][1]=val(1,1); for(int i=1;i<=n;i++) if(!zxf()&&!fxf()) break;//Air echo optimization //... } //...
Then count the minimum weight paths
Similarly, remember that G I, J (i+j ≤ N+1) g {I, J} (i+j \ Le N+1) gi,j(i+j ≤ N+1) denotes the number of minimum weight paths from (I, J) (I, J) to the axis of symmetry (x,y)(x+y==N+1)(x,y)(x+y==N+1)(x,y)(x+y==N+1).
First, find mn=min {f I, J} (i+j==N+1) Mn = \ min \ {f {I, J} \} (i+j==N+1) mn=min {fi, J} (i+j==N+1). Find all the (i,j)(i,j)(i,j) (I, J)) that satisfy fi, J (i+j==N+1) = = MNF {I, J} (i+j==N+1)==mn, let GI, J = 1g {I, J} = 1gi, j = 1. Then, because the shortest path will also go around, echo dp\texttt{dp}dp again to find the grid where the shortest path passes:
Repeat nnn times
From the axis of symmetry to the upper left corner, dp\texttt{dp}dp is pushed forward and backward.
Reverse dp\texttt{dp}dp from the upper left corner to the axis of symmetry.
If all FW I, J, K FW {I, J, K} FWI in the new round of reverberation, j. If K doesn't change, optimize - stop reverberating.
Code:
//... bool zxg(){//Reverse dp from top left corner to symmetric axis bool res=0; for(int i=3;i<=n+1;i++) for(int x=1;x<i;x++){ int y=i-x; if(f[x][y]+val(x-1,y)==f[x-1][y]&&g[x-1][y]>fw[x][y][0]) (g[x][y]+=g[x-1][y]-fw[x][y][0])%=mod,fw[x][y][0]=g[x-1][y],res=1; if(f[x][y]+val(x,y-1)==f[x][y-1]&&g[x][y-1]>fw[x][y][1]) (g[x][y]+=g[x][y-1]-fw[x][y][1])%=mod,fw[x][y][1]=g[x][y-1],res=1; } return res; } bool fxg(){//From the axis of symmetry to the upper left corner, the positive order of dp is inversely deduced. bool res=0; for(int i=n;i>=2;i--) for(int x=1;x<i;x++){ int y=i-x; if(f[x][y]+val(x+1,y)==f[x+1][y]&&g[x+1][y]>fw[x][y][2]) (g[x][y]+=g[x+1][y]-fw[x][y][2])%=mod,fw[x][y][2]=g[x+1][y],res=1; if(f[x][y]+val(x,y+1)==f[x][y+1]&&g[x][y+1]>fw[x][y][3]) (g[x][y]+=g[x][y+1]-fw[x][y][3])%=mod,fw[x][y][3]=g[x][y+1],res=1; } return res; } void dp(){ //... mn=inf; for(int i=1;i<=n;i++) mn=min(mn,f[i][n+1-i]); memset(g,0x00,sizeof g); for(int i=1;i<=n;i++) if(f[i][n+1-i]==mn) g[i][n+1-i]=1; memset(fw,0x00,sizeof fw); for(int i=1;i<=n;i++) if(!fxg()&&!zxg()) break; //... } //...
The final answer is g1,1g {1,1} g1,1, that is, the number of paths from (1,1) (1,1) to the minimum weight path lattice on the symmetry axis. That is, the minimum Ti, JT {I, J} Ti, J and the number of paths from (1,1) (1,1) (1,1) to (n, n) (n, n).
Code
#include <bits/stdc++.h> using namespace std; //@Start const int inf=0x3f3f3f3f; //@Debug void debug(int x,int y,int arr[][1010]){ for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) printf("%d%c",arr[i][j],"\n "[j<y]); } //@DP const int N=1010,mod=1e9+9; int n,a[N][N],f[N][N],g[N][N],mn,fw[N][N][4]; int val(int x,int y){ if(x+y==n+1) return a[x][y]; return a[x][y]+a[n-y+1][n-x+1]; } bool zxf(){ bool res=0; for(int i=3;i<=n+1;i++) for(int x=1;x<i;x++){ int y=i-x; if(min(f[x][y-1],f[x-1][y])+val(x,y)<f[x][y]) f[x][y]=min(f[x][y-1],f[x-1][y])+val(x,y),res=1; } return res; } bool fxf(){ bool res=0; for(int i=n;i>=2;i--) for(int x=1;x<i;x++){ int y=i-x; if(min(f[x][y+1],f[x+1][y])+val(x,y)<f[x][y]) f[x][y]=min(f[x][y+1],f[x+1][y])+val(x,y),res=1; } return res; } bool zxg(){ bool res=0; for(int i=3;i<=n+1;i++) for(int x=1;x<i;x++){ int y=i-x; if(f[x][y]+val(x-1,y)==f[x-1][y]&&g[x-1][y]>fw[x][y][0]) (g[x][y]+=g[x-1][y]-fw[x][y][0])%=mod,fw[x][y][0]=g[x-1][y],res=1; if(f[x][y]+val(x,y-1)==f[x][y-1]&&g[x][y-1]>fw[x][y][1]) (g[x][y]+=g[x][y-1]-fw[x][y][1])%=mod,fw[x][y][1]=g[x][y-1],res=1; } return res; } bool fxg(){ bool res=0; for(int i=n;i>=2;i--) for(int x=1;x<i;x++){ int y=i-x; if(f[x][y]+val(x+1,y)==f[x+1][y]&&g[x+1][y]>fw[x][y][2]) (g[x][y]+=g[x+1][y]-fw[x][y][2])%=mod,fw[x][y][2]=g[x+1][y],res=1; if(f[x][y]+val(x,y+1)==f[x][y+1]&&g[x][y+1]>fw[x][y][3]) (g[x][y]+=g[x][y+1]-fw[x][y][3])%=mod,fw[x][y][3]=g[x][y+1],res=1; } return res; } void dp(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); memset(f,0x3f,sizeof f); f[1][1]=val(1,1); for(int i=1;i<=n;i++) if(!zxf()&&!fxf()) break; // debug(n,n,f); mn=inf; for(int i=1;i<=n;i++) mn=min(mn,f[i][n+1-i]); memset(g,0x00,sizeof g); for(int i=1;i<=n;i++) if(f[i][n+1-i]==mn) g[i][n+1-i]=1; memset(fw,0x00,sizeof fw); for(int i=1;i<=n;i++) if(!fxg()&&!zxg()) break; printf("%d\n",g[1][1]); } //@Main int main(){ // freopen("100.in","r",stdin); scanf("%d",&n); while(n) dp(),scanf("%d",&n);//Multiple sets of test data return 0; }
I wish you all a happy study!
