首页 > > 程序设计 > C/C++ >

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

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

描述：

有一个地宫宝库是 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 3 2

1 2 3

2 1 5

程序应该输出：

#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;
}