蓝桥杯历届试题地库取宝（深搜dfs)

问题描述
　　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];//是否曾记录过 

      <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">==</span>n<span class="token operator">&amp;&amp;</span>y<span class="token operator">==</span>m<span class="token punctuation">)</span><span class="token comment" spellcheck="true">//&#x5230;&#x8FBE;&#x51FA;&#x53E3; </span>
    <span class="token punctuation">{</span> 
      <span class="token keyword">if</span><span class="token punctuation">(</span>sum<span class="token operator">==</span>k<span class="token operator">||</span><span class="token punctuation">(</span>sum<span class="token operator">==</span>k<span class="token number">-1</span><span class="token operator">&amp;&amp;</span>max<span class="token operator">&lt;</span>a<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token comment" spellcheck="true">//&#x5224;&#x65AD; &#x6301;&#x5B9D;&#x6570;&#x7B26;&#x5408;&#x6761;&#x4EF6;&#x6216;&#x518D;&#x52A0;&#x4E0A;&#x51FA;&#x53E3;&#x5B9D;&#x7269; &#x7B26;&#x5408; </span>
       <span class="token punctuation">{</span>jl<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">[</span>sum<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x8BB0;&#x5F55; </span>

         <span class="token keyword">return</span> jl<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">[</span>sum<span class="token punctuation">]</span><span class="token punctuation">;</span>
       <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>
    <span class="token keyword">else</span>
    <span class="token punctuation">{</span>
      <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token operator">&gt;</span>max<span class="token punctuation">)</span><span class="token comment" spellcheck="true">//&#x5F53;&#x6EE1;&#x8DB3;&#x53EF;&#x62FF;&#x8D77; &#x6761;&#x4EF6; </span>
      <span class="token punctuation">{</span>  t<span class="token operator">=</span>a<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment" spellcheck="true">//&#x6B64;&#x72B6;&#x6001; &#x53EF;&#x884C;&#x65B9;&#x6848;&#x6570; = &#x62FF;&#x8D77;&#x540E;&#x5411;&#x53F3; + &#x4E0D;&#x62FF;&#x8D77;&#x540E;&#x5411;&#x53F3; + &#x62FF;&#x8D77;&#x540E;&#x5411;&#x53F3;&#x4E0B; + &#x4E0D;&#x62FF;&#x8D77;&#x540E;&#x5411;&#x4E0B; </span>
      jl<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">[</span>sum<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">f</span><span class="token punctuation">(</span>x<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>y<span class="token punctuation">,</span>t<span class="token punctuation">,</span>sum<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>D<span class="token operator">+</span><span class="token function">f</span><span class="token punctuation">(</span>x<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>y<span class="token punctuation">,</span>max<span class="token punctuation">,</span>sum<span class="token punctuation">)</span>D<span class="token operator">+</span><span class="token function">f</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>y<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>t<span class="token punctuation">,</span>sum<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>D<span class="token operator">+</span><span class="token function">f</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>y<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>sum<span class="token punctuation">)</span>D<span class="token punctuation">;</span>
       <span class="token punctuation">}</span> 
      <span class="token keyword">else</span> jl<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">[</span>sum<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">f</span><span class="token punctuation">(</span>x<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>y<span class="token punctuation">,</span>max<span class="token punctuation">,</span>sum<span class="token punctuation">)</span>D<span class="token operator">+</span><span class="token function">f</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>y<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">,</span>sum<span class="token punctuation">)</span>D<span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5F53;&#x4E0D;&#x6EE1;&#x8DB3;&#x53EF;&#x62FF;&#x8D77; &#x6761;&#x4EF6;</span>
                   <span class="token comment" spellcheck="true">//&#x6B64;&#x72B6;&#x6001; &#x53EF;&#x884C;&#x65B9;&#x6848;&#x6570; = &#x4E0D;&#x62FF;&#x8D77;&#x540E;&#x5411;&#x53F3; + &#x4E0D;&#x62FF;&#x8D77;&#x540E;&#x5411;&#x4E0B;</span>
    <span class="token keyword">return</span> jl<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">[</span>sum<span class="token punctuation">]</span>D<span class="token punctuation">;</span> 
   <span class="token punctuation">}</span> 

<span class="token punctuation">}</span>
<span class="token keyword">return</span> jl<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">[</span>max<span class="token punctuation">]</span><span class="token punctuation">[</span>sum<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
}
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;
}