【Description】
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
【Input】
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
【Output】
输出最长区域的长度。
【Sample Input】
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
【Sample Output】
25
【Source】
SHTSC 2002
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | package pku1088; /**深度搜索+备忘录方法 / 动态规划 参考了pku牛人的解题报告*/ import java.util.*; public class Main { /** * @param args */ private static int[][] a = new int[101][101]; private static int[][] b = new int[101][101];// 备忘录 private static boolean[][] flag = new boolean[101][101]; private static int r, c; private static int[] tempx = { 1, 0, -1, 0 }; private static int[] tempy = { 0, -1, 0, 1 }; public static int trydo(int x, int y) { if (flag[x][y])// 如果已经有了,直接输出,备忘录方法快就快在这里 return b[x][y]; int max = 1, temp; for (int i = 0; i < 4; i++) {// 四个方向 int xx = x + tempx[i]; int yy = y + tempy[i]; if (xx >= 0 && xx < r && yy >= 0 && yy < c) {// 判断是否出界 if (a[xx][yy] < a[x][y]) {// 如果要到的点到本点低 temp = trydo(xx, yy);// 走下一个点 if (temp + 1 > max)// max = temp + 1; } } } flag[x][y] = true;// 已经走过 b[x][y] = max;// 存入备忘录 return max; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner cin = new Scanner(System.in); r = cin.nextInt(); c = cin.nextInt(); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { a[i][j] = cin.nextInt(); b[i][j] = 0; flag[i][j] = false; } } int max = 0; for (int i = 0; i < r; i++) {// 生成每个点的最大 for (int j = 0; j < c; j++) { if (trydo(i, j) > max) max = trydo(i, j); } } System.out.println(max); } } |