历届试题地宫取宝（记忆化搜索）

比眉伴天荒 2022-09-29 04:20 114阅读 0赞

问题描述

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 3 2  
1 2 3  
2 1 5

样例输出

思路：

自己尝试写的代码，虽然不全对，但还是要尝试自己写，真正比赛的时候才不会让你百度看别人的思路（当然也百度不到）：

代码：

#include<iostream>
    #include<algorithm>
    using namespace std;
    int n,m,k,map[51][51],cnt=0;
    void dfs(int x,int y,int num,int sum)
    {
    	int i,j;
    	if (x==n&&y==m) //到达终点
    	{
    		if (num == k)//物品数与规定的相等,一种结果 
    		{
    			cnt++;
    		}
    		if (num == k-1 && map[x][y] > sum) //最后地图价值 大于手中的，可以不拿,也是一种结果 
    		{
    			cnt++;
    		 } 
    		return ;
    	 }
    	if (x+1<=n) //可以向下走
    	{
    		if (map[x][y] > sum) //地图价值大于可以拿走 
    		{
    			dfs(x+1,y,num+1,map[x][y]);
    		}
    	    dfs(x+1,y,num,sum); //也可以不拿 
    	 } 
    	if (y+1<=m) //可以向右走
    	{
    		if (map[x][y] > sum)
    		{
    			dfs(x,y+1,num+1,map[x][y]);
    		}
    		dfs(x,y+1,num,sum);
    		
    	 }
    }
    int main()
    {
    	int i,j;
    	cin>>n>>m>>k;
    	for (i=1; i<=n; i++)
    	for (j=1; j<=m; j++)
    	 cin>>map[i][j];
    	 dfs(1,1,0,-1);//初始坐标，手中物品数，-1为手中的最大值
    	 cout<<cnt; 
    	return 0;
    }

学习的正确的代码：用4维数组记录每种状态，减少搜索次数

代码：

#include<iostream> 
    #include<string.h>
    #define N 1000000007
    using namespace std;
    typedef long long LL;
    LL n,m,k;
    LL map[50][50];
    LL flag[50][50][50][50];  //记录当在下标n,m处，手中有多少个物品，最大值是几， 
    LL dfs(LL x,LL y,LL sum,LL v)
    {
    	LL s=0,t;
    	if (flag[x][y][sum][v+1] != -1)//有值，直接返回结果，减少搜索次数
    	  return flag[x][y][sum][v+1]; 
    	if (x == n && y == m)//到达终点 
    	{
    		if (sum == k || (sum == k-1 && map[n][m] > v)) //物品数量和规定的k相等,或者最后一个地图价值大于手中的可以不拿 
    		{
    			flag[x][y][sum][v+1] = 1;
    			return 1;
    		 } 
    		else
    		  {
    		  	flag[x][y][sum][v+1] = -1;
    		  	return 0;
    		  }
    	}
    	if (x+1<=n) //向下走合法
    	{
    		if (map[x][y] > v) //地图价值大于手中价值 ,可拿
    		{
    			s += dfs(x+1,y,sum+1,map[x][y])%N;
    		 } 
    		s += dfs(x+1,y,sum,v)%N;
    	 } 
        if (y+1<=m) //向右走合法
    	{
    		if (map[x][y] > v)
    		{
    			s += dfs(x,y+1,sum+1,map[x][y])%N;
    		}
    			s += dfs(x,y+1,sum,v)%N;
    	 }
    	 flag[x][y][sum][v+1]  = s%N;
    	 return flag[x][y][sum][v+1];
    }
    int main()
    {
    	int i,j;
    	memset(flag,-1,sizeof(flag));
    	cin>>n>>m>>k;
    	for (i=1; i<=n; i++)
    	for (j=1; j<=m; j++)
    	{
    		cin>>map[i][j];
    	}
    	cout<<dfs(1,1,0,-1);//第一个下标，手中物品为0，初始设-1为最大值
    	return 0;
    }