1 //Accepted    184 KB    0 ms 2 //dp[i][j] 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 40; 8 int map[imax_n][imax_n]; 9 unsigned long long dp[imax_n][imax_n];10 int n;11 void Dp()12 {13     memset(dp,0,sizeof(dp));14     dp[0][0]=1;15     for (int i=0;i<n;i++)16     {17         for (int j=0;j<n;j++)18         {19             if (i==n-1 && j==n-1) continue;20             if (i+map[i][j]<n)21             dp[i+map[i][j]][j]+=dp[i][j];22             if (j+map[i][j]<n)23             dp[i][j+map[i][j]]+=dp[i][j];24         }25     }26     printf("%llu\n",dp[n-1][n-1]);27 }28 char s[imax_n];29 int main()30 {31     while (scanf("%d",&n),n+1)32     {33         for (int i=0;i<n;i++)34         {35             scanf("%s",s);36             for (int j=0;j<n;j++)37             map[i][j]=s[j]-‘0‘;38         }39         Dp();40     }41     return 0;42 }

 1 //Accepted    184 KB    0 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 const int imax_n = 40; 7 int map[imax_n][imax_n]; 8 unsigned long long dp[imax_n][imax_n]; 9 int n;10 void Dp()11 {12     memset(dp,0,sizeof(dp));13     dp[0][0]=1;14     for (int i=0;i<n;i++)15     {16         for (int j=0;j<n;j++)17         {18             for (int k=0;k<i;k++)19             {20                 if (k+map[k][j]==i)21                 dp[i][j]+=dp[k][j];22             }23             for (int k=0;k<j;k++)24             {25                 if (k+map[i][k]==j)26                 dp[i][j]+=dp[i][k];27             }28         }29     }30     printf("%llu\n",dp[n-1][n-1]);31 }32 int main()33 {34     char s[40];35     while (scanf("%d",&n),n+1)36     {37         for (int i=0;i<n;i++)38         {39             scanf("%s",s);40             for (int j=0;j<n;j++)41             map[i][j]=s[j]-‘0‘;42         }43         Dp();44     }45     return 0;46 }