蓝桥杯 历届试题 地库取宝（深搜 dfs)----------C语言—菜鸟级

/*问题描述
　　X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，
小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入格式
　　输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)

接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
输出格式
　　要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
样例输入
2 2 2
1 2
2 1
样例输出
2
样例输入
2 3 2
1 2 3
2 1 5
样例输出
14
思路 ：记忆法深搜

*/

#include<stdio.h>
#include <string.h>
int a[51][51];//地宫 
long long jl[51][51][15][15];//记录获取数据jl[x][y][此状态最大价值][此状态持宝数]; 
#define D %1000000007
int n,m,k;
long int cs=0;
long long f(long int x,long int y,long int max,long int sum)
{  int i,j,t,s;
      if(x<=n&&y<=m&&sum<=k)//地宫范围  及优化 持宝数超出直接过 
	  { if(jl[x][y][max][sum]!=-1)return jl[x][y][max][sum];//是否曾记录过 
	     
		  if(x==n&&y==m)//到达出口 
	    { 
		  if(sum==k||(sum==k-1&&max<a[x][y]))//判断 持宝数符合条件或再加上出口宝物 符合 
		   {jl[x][y][max][sum]=1;//记录 
		    
		     return jl[x][y][max][sum];
		   }
	      
	    }
		else
		{
		  if(a[x][y]>max)//当满足可拿起 条件 
          {  t=a[x][y]; //此状态 可行方案数 = 拿起后向右 + 不拿起后向右 + 拿起后向右下 + 不拿起后向下 
		  jl[x][y][max][sum]=f(x+1,y,t,sum+1)D+f(x+1,y,max,sum)D+f(x,y+1,t,sum+1)D+f(x,y+1,max,sum)D;
           } 
          else jl[x][y][max][sum]=f(x+1,y,max,sum)D+f(x,y+1,max,sum)D;//当不满足可拿起 条件
                       //此状态 可行方案数 =  不拿起后向右 + 不拿起后向下
        return jl[x][y][max][sum]D; 
       } 
        
    }
    return jl[x][y][max][sum]=0;
}


int main()
{int i,j;
  memset(jl,-1,sizeof(jl));//此处一定不能标记为 0 因为可能会无解 
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
 {scanf("%d",&a[i][j]);
 a[i][j]++;
 }
 printf("%lld\n",f(1,1,0,0));


return 0;
} 

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79767270