【HDOJ】1978 How many ways

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAXNUM 105
 5 
 6 int map[MAXNUM][MAXNUM], ways[MAXNUM][MAXNUM], n, m;
 7 
 8 int dfs(int x, int y) {
 9     int i, j, way=0;
10 
11     if (ways[x][y])
12         return ways[x][y];
13 
14     for (i=0; i<=map[x][y]; ++i) {
15         for (j=0; i+j<=map[x][y]; ++j) {
16             if (i==0 && j==0)
17                 continue;
18             if (x+i>=n || y+j>=m)
19                 continue;
20             way += dfs(x+i, y+j);
21             if (way >= 10000)
22                 way %= 10000;
23         }
24     }
25 
26     ways[x][y] = way;
27 
28     return way;
29 }
30 
31 int main() {
32     int t;
33     int i, j;
34 
35     scanf("%d", &t);
36 
37     while (t--) {
38         scanf("%d %d", &n, &m);
39         memset(ways, 0, sizeof(ways));
40         for (i=0; i<n; ++i)
41             for (j=0; j<m; ++j)
42                 scanf("%d", &map[i][j]);
43         ways[n-1][m-1] = 1;
44         i = dfs(0, 0);
45         printf("%d\n", i);
46     }
47 
48     return 0;
49 }