深度优先搜索——地宫取宝

2018-06-17 21:49:11来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

描述:

有一个地宫宝库是 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 <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N=1000000007;
int ans,n,m,k;//n行m列 k个宝贝 
int d[51][51][13][14];//保存状态 
int p[51][51];//地图中每个地点宝贝的价值 

int dfs(int x,int y,int num,int maxvalue){
    if(d[x][y][num][maxvalue+1]!=-1){//如果状态库里有记录就直接在库里查找,不用递归计算 
        return d[x][y][num][maxvalue+1]; //我不明白为什么要坐标+1 
        //传进去的值是-1啊,为了防止越界当然要加一
    }
    int t=0;//这个估计是行动方案数的记录 
    if(x==n-1&&y==m-1){//到达终点 
        if(p[x][y]>maxvalue){//价值比现有的高 
            if(num==k||num==k-1) t++; //刚好或差一件都可以+1
        }
        else if(num==k){//刚好就可以+1 
            t++;
        }
        //cout << "终点" <<x << "," << y << " "<< num << " "<< maxvalue<< " " << t <<endl; 
        d[x][y][num][maxvalue+1]=t;
        return d[x][y][num][maxvalue+1];//这个返回暂时没看懂 
    } 
    
    if(x+1<n){//如果再走一步不越界 
        if(p[x][y]>maxvalue){//价值大于现在 执行下面两种情况 
            t+=dfs(x+1,y,num+1,p[x][y]);
            t%=N;
            t+=dfs(x+1,y,num,maxvalue);
            t%=N;    
        }
        else{//小于就只有一种情况 继续走 
            t+=dfs(x+1,y,num,maxvalue);
            t%=N;
        }
    }
    
    if(y+1<m){//如果再走一步不越界 
    if(p[x][y]>maxvalue){//价值大于现在 执行下面两种情况 
        t+=dfs(x,y+1,num+1,p[x][y]);
        t%=N;
        t+=dfs(x,y+1,num,maxvalue);
        t%=N;    
        }
    else{//小于就只有一种情况 继续走 
        t+=dfs(x,y+1,num,maxvalue);
        t%=N;
        }
    }
    //cout << "中途" <<x << "," << y << " "<< num << " "<< maxvalue<< " " << t <<endl;  
    d[x][y][num][maxvalue+1]=t;
    return d[x][y][num][maxvalue+1];//max坐标+1 
}

int main(){
    cin >> n >> m >> k;
    for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
           cin >> p[i][j];
//    for(int i=0;i<51;++i)
//        for(int j=0;j<51;++j)
//            for(int p=0;p<13;++p)  
//                for(int q=0;q<14;++q)
//                 d[i][j][p][q]=-1;            
    memset(d,-1,sizeof(d));//全部赋值-1 

    cout << dfs(0,0,0,-1); //从坐标(0,0) 宝物数0 最大值为-1开始  
    
    return 0;
}
实现代码

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Travelling HDU - 3001

下一篇:HDU_5527_Too Rich