pku2704 Pascal's Travels

基础DP
 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int i, j, k, n, map[36][36];
 6     long long dp[36][36];
 7     char c;
 8     while(scanf("%d%*c", &n), ~n)
 9     {
10         //init
11         for(i=1; i<=n; i++)
12         {
13             for(j=1; j<=n; j++)
14             {
15                 scanf("%c", &c);
16                 map[i][j] = c-'0';
17                 dp[i][j] = 0;
18             }
19             getchar();
20         }
21         dp[1][1] = 1;
22         
23         for(i=1; i<=n; i++)
24         {
25             for(j=1; j<=n; j++)
26             {
27                 //search_left
28                 for(k=1; k<j; k++)
29                 {
30                     if(k + map[i][k] == j)
31                     {
32                         dp[i][j] += dp[i][k];
33                     }
34                 }
35                 //search_up
36                 for(k=1; k<i; k++)
37                 {
38                     if(k + map[k][j] == i)
39                     {
40                         dp[i][j] += dp[k][j];
41                     }
42                 }
43                 //printf("%d ", dp[i][j]);
44             }
45             //printf("\n");
46         }
47         printf("%lld\n", dp[n][n]);
48     }
49     return 0;
50 }