| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 479 人关注过本帖
标题:蓝桥杯 历届试题 地宫取宝
只看楼主 加入收藏
troyzyc
Rank: 1
等 级:新手上路
帖 子:108
专家分:0
注 册:2016-7-4
结帖率:56.6%
  已结贴   问题点数:5  回复次数:1   
蓝桥杯 历届试题 地宫取宝
问题描述
  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;
}
2018-03-06 10:04
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:50
帖 子:4972
专家分:13940
注 册:2016-10-22
  得分:4 
这题我看过,网上搜到答案用四维数组,似乎是回溯算法,找找资料对比一下,可以找到的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-03-07 19:10







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.023652 second(s), 9 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved