Description

You have a grid of n rows and n columns. Each of the unit squares contains a non-zero digit. You walk from the top-left square to the bottom-right square. Each step, you can move left, right, up or down to the adjacent square (you cannot move diagonally), but you cannot visit a square more than once. There is another interesting rule: your path must be symmetric about the line connecting the bottom-left square and top-right square. Below is a symmetric path in a 6 x 6 grid.

Your task is to find out, among all valid paths, how many of them have the minimal sum of digits?

 

There will be at most 25 test cases. Each test case begins with an integer n ( 2n100). Each of the next n lines contains n non-zero digits (i.e. one of 1, 2, 3, ..., 9). These n² integers are the digits in the grid. The input is terminated by a test case with n = 0, you should not process it.

 

For each test case, print the number of optimal symmetric paths, modulo 1,000,000,009.

 

21 11 131 1 11 1 12 1 10

 

23 思路：要求是要关于那条线对称的，所一把上半角和下半角叠加起来，然后求到那条线的最短路即可，用迪杰斯特拉求。建图也比较简单,就是每个点向四个方向的点连边 。在求最短路的时候开一个数组记录当前走到该点的最短路有多少条就行，最后求到斜边点上等于最短路的种数和即可。 复杂度n*n

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 int ma[200][200]; 10 typedef struct pp 11 { 12 int x; 13 int y; 14 int cost; 15 int id; 16 bool flag; 17 } ss; 18 const int mod=1e9+9; 19 typedef long long LL; 20 LL sum[10005]; 21 LL d[10005]; 22 bool flag[10005]; 23 ss node[10005]; 24 vector
            
             vec[10005]; 25 int dd[200][200]; 26 void dj(int n,int id); 27 int main(void) 28 { 29 int i,j,k; 30 while(scanf("%d",&k),k!=0) 31 { 32 memset(dd,-1,sizeof(dd)); 33 memset(flag,0,sizeof(flag)); 34 memset(sum,0,sizeof(sum)); 35 for(i=0;i<10005;i++) 36 vec[i].clear(); 37 for(i=0; i
             
              =0) 75 { 76 ss cc; 77 cc.x=i-1; 78 cc.y=j; 79 cc.id=dd[i-1][j]; 80 cc.cost=ma[i-1][j]; 81 vec[id].push_back(cc); 82 cc.x=i; 83 cc.y=j; 84 cc.id=dd[i][j]; 85 cc.cost=ma[i][j]; 86 vec[dd[i-1][j]].push_back(cc); 87 } 88 if(j-1>=0) 89 { 90 ss cc; 91 cc.x=i; 92 cc.y=j-1; 93 cc.id=dd[i][j-1]; 94 cc.cost=ma[i][j-1]; 95 vec[id].push_back(cc); 96 cc.x=i; 97 cc.y=j; 98 cc.id=dd[i][j]; 99 cc.cost=ma[i][j];100 vec[dd[i][j-1]].push_back(cc);101 }102 if(i+1
              
               d[i])140 {141 maxx=d[i];142 }143 }144 }145 LL akk=0;146 for(i=0; i
               
                d[l]+pp.cost)202 d[pp.id]=d[l]+pp.cost;203 }204 }205 }