HDU1978How Many Ways 记忆化dfs+dp

 1 /*记忆化dfs+dp
 2 dp[i][j]代表达到这个点的所有路的条数，那么所有到达终点的路的总数就是这dp[1][1]加上所有他所能到达的点的
 3 所有路的总数
 4 */
 5 
 6 #include<stdio.h>
 7 #include<string.h>
 8 #include<algorithm>
 9 using namespace std;
10 const int maxn=110;
11 int map[maxn][maxn],vis[maxn][maxn];
12 int dp[maxn][maxn];
13 int n,m;
14 int ok(int x,int y)
15 {
16     if(x>=1 && x<=n && y>=1 && y<=m) return 1;
17     return 0;
18 }
19 void init()
20 {
21     memset(dp,0,sizeof(dp));
22     memset(vis,0,sizeof(vis));
23 }
24 int dfs(int x,int y)
25 {
26     if(dp[x][y]) return dp[x][y];
27     if(x==n && y==m) return dp[x][y]=1;
28     int i,j;
29     int num=map[x][y];
30     for(i=0;i<=num;i++)
31     for(j=0;j<=num-i;j++)
32     {
33         int nx=x+i;
34         int ny=y+j;
35         if(ok(nx,ny) && !vis[nx][ny])
36         {
37             vis[nx][ny]=1;
38             dp[x][y]=(dp[x][y]+dfs(nx,ny))%10000;
39             vis[nx][ny]=0;
40         }
41     }
42     return dp[x][y]%10000;
43 }
44 int main()
45 {
46     int i,j;
47     int t;
48     scanf("%d",&t);
49     while(t--)
50     {
51         scanf("%d%d",&n,&m);
52         for(i=1;i<=n;i++)
53         for(j=1;j<=m;j++)
54         scanf("%d",&map[i][j]);
55         init();
56         vis[1][1]=1;
57         int sum=dfs(1,1);
58         printf("%d
",sum);
59     }
60     return 0;
61 }