2014年Java方向C组第九题

标题：地宫取宝

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

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。

解析：

方案一：

static int n;  //矩阵n行
static int m; //矩阵m列
static int k; //要求取宝贝的数量
static int[][] arr; //定义矩阵的二维数组
static long result=0; //答案  

//rowIndex:当前X轴坐标;colIndex:当前Y轴坐标;
//max:行走过程中最大价值;count:手中宝贝数量
public static void move(int rowIndex,int colIndex,int max,int count)
{
    if(rowIndex >= n || colIndex >= m || count > k) //当走出矩阵或者宝贝数量过多则退出函数
        return;
    if(rowIndex == n-1 && colIndex == m-1) //走到最后一格格子
    {
        //当宝贝数量已经符合题意，则最后一次不拿宝贝
        //当宝贝差一个并且最后一格格子价值高于最大值，则拿起最后一格宝贝符合题意
        if(count == k || (count == k-1 && arr[rowIndex][colIndex] > max)) 
        {
            result++;
            result = result % 1000000007;
        }
    }
    if(arr[rowIndex][colIndex] > max) //当前格子价格大于任意宝贝价格
    {
            move(rowIndex+1,colIndex,arr[rowIndex][colIndex],count+1); //右走,拿起宝贝
            move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
            move(rowIndex,colIndex+1,arr[rowIndex][colIndex],count+1); //下走,拿起宝贝    
            move(rowIndex,colIndex+1,max,count);     //下走，不拿宝贝
    }
    else
    {
        move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
        move(rowIndex,colIndex+1,max,count);     //下走，不拿宝贝
    }   
}

public static void main(String[] args) 
{
    Scanner input  = new Scanner(System.in);
    n = input.nextInt();  //矩阵n行
    m = input.nextInt(); //矩阵m列
    arr = new int[n][m]; //定义矩阵的二维数组
    k = input.nextInt(); //取K件宝贝
    //循环输入矩阵中每件宝贝的价值
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            arr[i][j] = input.nextInt();
        }
    }
    move(0,0,-1,0); //max值给-1因为宝物价值可以为0
    System.out.println(result );
}

方案一有很多重复递归计算，效率较低，例如，如下数组：

1   2   3
4   5   6
7   8   9

如果数据定位在5的位置，并且递归函数的四个参数完全相同的情况下，也就是坐标相同，最大值相同，宝贝数量也相同，只需要向里层递归一次求得结果即可，不需要每次重复递归计算。

方案二：

（1）定义四维数组，存储递归函数四个参数取不同值的时候到右下角的方案数量，即答案，判断是否经历过计算，避免重复计算，提高运行效率。

（2）1到9的数量=2到9数量+4到9的数量；2到9数量=3到9的数量+5到9的数量；......,所以在每次递归调用的时候进行累加计算。

static int n;  //矩阵n行
static int m; //矩阵m列
static int k; //要求取宝贝的数量
static int[][] arr; //定义矩阵的二维数组
static long data[][][][] = new long[55][55][15][15];
//rowIndex:当前X轴坐标;colIndex:当前Y轴坐标;
//max:行走过程中最大价值;count:手中宝贝数量
public static long move(int rowIndex,int colIndex,int max,int count)
{
    if(data[rowIndex][colIndex][max+1][count] != -1) 
        return data[rowIndex][colIndex][max+1][count];
    long result=0; //答案 
    if(rowIndex >= n || colIndex >= m || count > k) //当走出矩阵或者宝贝数量过多则退出函数
        return 0;
    if(rowIndex == n-1 && colIndex == m-1) //走到最后一格格子
    {
        //当宝贝数量已经符合题意，则最后一次不拿宝贝
        //当宝贝差一个并且最后一格格子价值高于最大值，则拿起最后一格宝贝符合题意
        if(count == k || (count == k-1 && arr[rowIndex][colIndex] > max)) 
            return 1;
        return 0;
    }
    if(arr[rowIndex][colIndex] > max) //当前格子价格大于任意宝贝价格
    {
            result += move(rowIndex+1,colIndex,arr[rowIndex][colIndex],count+1); //右走,拿起宝贝
            result += move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
            result += move(rowIndex,colIndex+1,arr[rowIndex][colIndex],count+1); //下走,拿起宝贝  
            result += move(rowIndex,colIndex+1,max,count);   //下走，不拿宝贝
    }
    else
    {
        result += move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
        result += move(rowIndex,colIndex+1,max,count);   //下走，不拿宝贝
    }   
    //System.out.println(rowIndex+","+colIndex+","+max+","+count+"="+result);
    data[rowIndex][colIndex][max+1][count] = result%1000000007;
    return result;
}
//初始化data数据全部为-1
public static void InitData()
{
    for (int a = 0; a < 55; a++) {
        for (int b = 0; b < 55; b++) {
            for (int c = 0; c < 15; c++) {
                for (int d = 0; d < 15; d++) {
                    data[a][b][c][d] = -1;
                }
            }
        }
    }
}

public static void main(String[] args) 
{
    Scanner input  = new Scanner(System.in);
    n = input.nextInt();  //矩阵n行
    m = input.nextInt(); //矩阵m列
    arr = new int[n][m]; //定义矩阵的二维数组
    k = input.nextInt(); //取K件宝贝
    //循环输入矩阵中每件宝贝的价值
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            arr[i][j] = input.nextInt();
        }
    }
    InitData();
    long r = move(0,0,-1,0); //max值给-1因为宝物价值可以为0
    System.out.println(r );
}