地宫取宝蓝桥杯记忆化搜索DFS

 1 #include 
 2 #include <string.h>
 3 #define N 1000000007
 4 int n,m,k;
 5 int map[50][50];
 6 int vis[50][50][15][15];//vis数组中记录的是状态   xy坐标 拥有宝物数量 拥有宝物的最大值(这4个可以详尽唯一的描述没一种可能) 
 7 //  如   vis[3][4][5][6]=7 即当在map[3][4]且身上有5件宝物 宝物的最大值是6 是到达终点有7中路径
 8 
 9 int dfs(int x,int y,int num,int max)//当前位置   拥有宝物的数量 拥有的宝物的最大值
10 {
11     if (vis[x][y][num][max+1]!=-1)//因为宝物有可能为0所以定义max时用最小值-1 这就导致无法作为下标使用  实际上如果测试数据中宝物价值没有0 将所有的+1 去掉也是可以的
12     {
13         return vis[x][y][num][max+1]; 
14     }//记忆化的记忆就指的是上面
15     if(x==n&&y==m)
16     {
17         if(num==k)return vis[x][y][num][max+1]=1;//满足条件 当前点到目标有1种方案
18         else if(num==k-1&&maxreturn vis[x][y][num][max+1]=1;//同样满足条件 当前点到目标有1种方案
19         else return vis[x][y][num][max+1]=0;//不满足条件 当前点到目标有0种方案
20     }
21     long long s=0;
22     if(x+1<=n)//可以向下走
23     {
24         if (max<map[x][y])
25         {
26             s+=dfs(x+1,y,num+1,map[x][y]);
27             s%N;
28         }
29             s+=dfs(x+1,y,num,max);
30             s%N;
31     }
32     if(y+1<=m)
33     {
34         if (max<map[x][y])
35         {
36             s+=dfs(x,y+1,num+1,map[x][y]);
37             s%N;
38         }
39             s+=dfs(x,y+1,num,max);
40             s%N;
41     }
42     return vis[x][y][num][max+1]=s%N;;
43 }
44 int main(int argc, char const *argv[])
45 {
46 //    freopen("C:\\Users\\cong\\Desktop\\input.txt","r",stdin); 
47 //    freopen("C:\\Users\\cong\\Desktop\\output.txt","w",stdout); 
48 
49     scanf("%d%d%d",&n,&m,&k);
50 
51     for (int i = 1;i<=n;i++)
52     {
53         for (int j = 1; j <=m; j++)
54         {
55             scanf("%d",&map[i][j]);
56         }
57     }//初始地宫
58     memset(vis,-1,sizeof(vis));
59     dfs(1,1,0,-1);
60     printf("%d",vis[1][1][0][0]);
61 
62     return 0;
63 }