蓝桥杯 历届试题 地宫取宝
问题描述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>
#define N 1000000007
int n,m,k;
long long count=0;
int map[60][60];
void dfs(int x,int y,int num,int max)
{
int maxx=max;
int h,tx,ty;
int dir[2][2]={{0,1},{1,0}}; //{0,1}向右走，{1,0}向下走
if(x==n&&y==m) //结束条件：当到达最后终点时
{
if(num==k) //在达到终点前就已经拿到k个宝贝
{
count++;
count=count%N;
return;
}
else if(num==k-1 && max<map[x][y]) //在达到终点前一步拿到k-1个宝贝并且最后一步还能拿一个宝贝
{
count++;
count=count%N;
return;
}
else
return;
}
for(h=0;h<=1;h++) //两个方向的选择
{
tx=x+dir[h][0]; //h=0时，向右走；h=1，向下走; (tx,ty)下一步的位置
ty=y+dir[h][1];
if(tx>n || tx<1 ||ty>m ||ty<1) //保证下一步的位置不出界
continue; //出界的话就换一个方向走
if(max<map[x][y]) //若拿走宝贝
{
dfs(tx,ty,num+1,map[x][y]);
}
dfs(tx,ty,num,maxx); //若不拿走宝贝
}
return ;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
}
}
dfs(1,1,0,0);//起始认为从(1,1)开始进入，手中没有宝贝，宝贝最大值设置为0
printf("%lld\n",count%N);
return 0;
}
~
