SDUT1570 C旅行

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1570

递归求解

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int count = 0;
 4 int a[21][21];
 5 int h, w;
 6 void road(int m, int n)
 7 {
 8     int i, j;    
 9     if(m == 1&&n == w)
10     {
11         count++;
12         return ;
13     }
14     else
15         if(m==0||n == w+1)
16             return ;
17     if(a[m-1][n]==0)
18         road(m-1, n);
19     if(a[m][n+1]==0)
20         road(m, n+1);
21 }
22 int main()
23 {
24     int i, j, k;
25     scanf("%d%d", &h, &w);
26     for(i = 1; i <= h ; i++)
27         for(j = 1 ; j <= w ; j++)
28         scanf("%d", &a[i][j]);
29     road(h, 1);
30     printf("%d\n", count);
31     return 0;
32 }

之前请教的qc用搜索做的

现在请教了cz 用dp做了一遍

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 int main()
 4 {
 5     int h, w, a[23][23], i, j, num[23][23];
 6     scanf("%d%d", &h, &w);
 7     memset(num, 0, sizeof(num));
 8     for(i = 1 ; i <= h ; i++)
 9     for(j = 1 ; j <= w ; j++)
10     {
11         scanf("%d", &a[i][j]);
12     }
13     for(i = 1 ;i <= h ; i++)
14     {
15         num[h][0] = 0;
16         num[h][w+1] = 0;
17     }
18     for(i = 1 ; i <= w ; i++)
19     {
20         if(num[0][w] == 1)
21         num[0][w] = 1;
22         else
23         num[0][w] = 0;
24         num[h+1][w] = 0;
25     }
26     num[0][w]=1;
27     for(i = 1 ; i <= h ; i++)
28     for(j = w ; j >= 1  ; j--)
29     {
30         if(a[i][j] == 0)
31         {
32             num[i][j] = num[i-1][j]+num[i][j+1];//这个是主要部分
33         }
34     }
35     printf("%d\n", num[h][1]);
36     return 0;
37 }