IT工程師數位筆記本

題目：矩形滑雪場
trs喜歡滑雪。他來到了一個滑雪場，這個滑雪場是一個矩形，為了簡便，我們用r行c列的矩陣來表示每塊地形。
為了得到更快的速度，滑行的路線必須向下傾斜。        
例如樣例中的那個矩形，可以從某個點滑向上下左右四個相鄰的點之一。例如24-17-16-1，其實25-24-23…3-2-1更長，事實上這是最長的一條。
輸入格式：
第1行:  兩個數字r，c(1< =r,c< =100)，表示矩陣的行列。 第2..r+1行:每行c個數，表示這個矩陣。
輸出格式：
僅一行:  輸出1個整數，表示可以滑行的最大長度。

樣例輸入
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
樣例輸出
25

//解題思路：將二維數組轉換為一維數組，求一維數組的最長遞增子序列
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Solution3 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        Point[] array = new Point[n * m];
        int num = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                array[num] = new Point();
                array[num].x = i;
                array[num].y = j;
                array[num].h = input.nextInt();
                num++;
            }
        }
        Arrays.sort(array, new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                return o1.h - o2.h;
            }

        });
        int[] dp = new int[n * m];
        int max = 1;
        for (int i = 0; i < n * m; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (check(array[i], array[j])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(dp[i], max);
                }
            }

        }

        System.out.println(max);
    }

    public static boolean check(Point p1, Point p2) {
        if (((p1.x == p2.x && Math.abs(p1.y - p2.y) == 1) || (p1.y == p2.y && Math.abs(p1.x - p2.x) == 1))
                && (p1.h > p2.h)) {
            return true;
        } else {

            return false;
        }
    }
}

class Point {
    int x;
    int y;
    int h;
}