蓝桥杯-地宫取宝

/*9_题目 http://rapheal.iteye.com/blog/1526863 标题：地宫取宝 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，否则按无效代码处理。 */ import java.util.Scanner; public class Main9 { private static int count = 0; //start实际件数 end设定的件数，max手中的最大值 ，s1矩阵, 总的x1, 总的 y1 public void remove(int start, int end, int max, int s1[][], int x, int y, int x1, int y1) { if (start > end) return; if (x == x1 - 1 && y == y1 - 1) { if (start == end) { count++; } else { if (start == end - 1 && s1[x][y] > max) count++; } } if (x + 1 < x1) { if (s1[x][y] > max) { remove(start + 1, end, s1[x][y], s1, x + 1, y, x1, y1); remove(start, end, max, s1, x + 1, y, x1, y1); } else { remove(start, end, max, s1, x + 1, y, x1, y1); } } if (y + 1 < y1) { if (s1[x][y] > max) { remove(start + 1, end, s1[x][y], s1, x, y + 1, x1, y1); remove(start, end, max, s1, x, y + 1, x1, y1); } else { remove(start, end, max, s1, x, y + 1, x1, y1); } } } public static void main(String args[]) { int a, b, c; Scanner input = new Scanner(System.in); a = input.nextInt(); b = input.nextInt(); c = input.nextInt(); int[][] s = new int[a][b]; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { s[i][j] = input.nextInt(); } } Main9 A = new Main9(); A.remove(0, c, -1, s, 0, 0, a, b); System.out.println(count % 1000000007); } }