地宫夺宝 java

川长思鸟来 2022-07-16 00:18 132阅读 0赞

地宫取宝  
    时间限制：1.0s   内存限制：256.0MB
        
    问题描述
    　　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

## 锦囊妙计 ##

在做地宫夺宝之前，请先思考一下,从A到B共有多少种方法

AàB的算法有很多，最简单的就是排列组合，但这样做与地宫夺宝就没什么关系了。

看了下面的图后你是否有了什么想法？

import java.util.Scanner;
    
    public class Main {
    
    	private static int K = 12;
    	private static int[][] bb ;
    	private static int[][][][] cc ;
    	private static int m, n, k;
    	
    	public static void main(String[] args) {
    		int i, j;
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		m = sc.nextInt();
    		k = sc.nextInt();
    		//储存矩阵中的数据n为行 m为列
    		bb = new int[n][m];
    		//储存在当前位置某一max某一宝物数量有多少种方法
    		//cc[1][2][5][3]=4；就是在第2行第3列，当手中最大宝物为5、宝贝数为3的方法有4种
    		cc = new int[n][m][K][K];
    		
    //		初始化cc数组
    //		
    		init();
    		
    //		为bb【】赋值
    		for (i = 0; i < n; i++) {
    			for (j = 0; j < m; j++) {
    				bb[i][j] = sc.nextInt();
    			}
    		}
    		
    		fds(0, 0, -1, 0);
    		
    		System.out.println(cc[0][0][0][0]%1000000007);
    	}
    
    	private static int fds(int i, int j, int max, int count) {
    		
    		//这个if语句是用于加速程序的运行，已经计算的格子，就不必在计算一次，直接返回。
    		if (cc[i][j][max + 1][count] != 0) {
    			return cc[i][j][max + 1][count];
    		}
    		int sum=0;
    		//最后一个格
    		if(i==n-1 && j==m-1){
    //			1、手中的宝物刚好k件，就不必关心最后一个格的宝物
    //			2、手中的宝物为k-1件，只有最后一个格的宝物大于手中最大宝物
    //			满足这两个条件，则夺宝成功
    			if(count==k||(count==k-1 && bb[i][j]>max)) 
    				sum++;
    			return cc[i][j][max+1][count]=sum;
    		}
    		//向下走
    		if(i<n-1){
    			if(bb[i][j]>max){
    //				该格子中的宝物大于手中宝物的最大值，并取出宝物
    				sum += fds(i+1,j,bb[i][j],count+1);
    				sum%=1000000007;
    			}
    //			无论宝物有多大，都不取。
    			sum += fds(i+1,j,max,count);
    			sum%=1000000007;
    		}
    	
    		//向右走
    		if(j <m-1){
    			if(bb[i][j]>max){
    //				该格子中的宝物大于手中宝物的最大值，并取出宝物
    				sum += fds(i,j+1,bb[i][j],count+1);
    				sum%=1000000007;
    			}
    //			无论宝物有多大，都不取。
    			sum += fds(i,j+1,max,count);
    			sum%=1000000007;
    		}
    		return cc[i][j][max+1][count]=sum%1000000007;
    
    	}
    	
    	public static void init() {
    		int i, j, r, s;
    		for (i = 0; i < n; i++) {
    			for (j = 0; j < m; j++) {
    				for (r = 0; r < K; r++) {
    					for (s = 0; s < K; s++) {
    						cc[i][j][r][s]=-1;
    					}
    				}
    
    			}
    		}
    	}
    }