leetcode 329 矩阵中的最长递增路径

package com.example.lettcode.dailyexercises;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Class LongestIncreasingPath
 * @Description 329 矩阵中的最长递增路径
 * 给定一个整数矩阵，找出最长递增路径的长度。
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
 * 示例 1:
 * 输入: nums =
 * [
 * [9,9,4],
 * [6,6,8],
 * [2,1,1]
 * ]
 * 输出: 4
 * 解释: 最长递增路径为 [1, 2, 6, 9]。
 * 示例 2:
 * 输入: nums =
 * [
 * [3,4,5],
 * [3,2,6],
 * [2,2,1]
 * ]
 * 输出: 4
 * 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
 * @Author
 * @Date 2020/7/26
 **/
public class LongestIncreasingPath {
    // 只利用深度优先会导致超时，所以需要记忆已经搜索过的位置
    static Map<Long, Integer> map = new HashMap<>();

    /**
     * dfs
     */
    public static int longestIncreasingPath(int[][] matrix) {
        // 静态变量每次使用前需要清空
        map.clear();
        if (matrix == null || matrix.length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int ans = 0;
        // 从任意起点
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans = Math.max(ans, dfs(matrix, i, j));
            }
        }
        return ans;
    }

    /**
     * 返回遍历到当前位置时所能获取的最大长度
     * 不需要标记是否遍历过，因为需要递增条件，至多搜索过一次
     * 记忆化：标记某个位置所能取得的最大长度，提高遍历效率
     */
    public static int dfs(int[][] matrix, int i, int j) {
        // 标记当前位置已遍历过，可以直接获取当前位置允许到达的最大长度
        long key = (long) i << 32 | j;		// 转换为long
        if (map.containsKey(key)) {
            return map.get(key);
        }
        int tmp = matrix[i][j];
        int maxLen = 1;
        if (i + 1 < matrix.length && matrix[i + 1][j] > tmp) {
            maxLen = Math.max(maxLen, dfs(matrix, i + 1, j) + 1);
        }
        if (i - 1 >= 0 && matrix[i - 1][j] > tmp) {
            maxLen = Math.max(maxLen, dfs(matrix, i - 1, j) + 1);
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > tmp) {
            maxLen = Math.max(maxLen, dfs(matrix, i, j + 1) + 1);
        }
        if (j - 1 >= 0 && matrix[i][j - 1] > tmp) {
            maxLen = Math.max(maxLen, dfs(matrix, i, j - 1) + 1);
        }
        map.put(key, maxLen);
        return maxLen;
    }
}

// 测试用例
public static void main(String[] args) {
	int[][] matrix = new int[][]{
			{9, 9, 4},
			{6, 6, 8},
			{2, 1, 1}
	};
	int ans = longestIncreasingPath(matrix);
	System.out.println("LongestIncreasingPath demo01 reult:" + ans);

	matrix = new int[][]{
			{3, 4, 5},
			{3, 2, 6},
			{2, 2, 1}
	};
	ans = longestIncreasingPath(matrix);
	System.out.println("LongestIncreasingPath demo02 reult:" + ans);

	matrix = new int[][]{
			{1, 2},
	};
	ans = longestIncreasingPath(matrix);
	System.out.println("LongestIncreasingPath demo12 reult:" + ans);

	matrix = new int[][]{
			{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
			{19, 18, 17, 16, 15, 14, 13, 12, 11, 10},
			{20, 21, 22, 23, 24, 25, 26, 27, 28, 29},
			{39, 38, 37, 36, 35, 34, 33, 32, 31, 30},
			{40, 41, 42, 43, 44, 45, 46, 47, 48, 49},
			{59, 58, 57, 56, 55, 54, 53, 52, 51, 50},
			{60, 61, 62, 63, 64, 65, 66, 67, 68, 69},
			{79, 78, 77, 76, 75, 74, 73, 72, 71, 70},
			{80, 81, 82, 83, 84, 85, 86, 87, 88, 89},
			{99, 98, 97, 96, 95, 94, 93, 92, 91, 90},
			{100, 101, 102, 103, 104, 105, 106, 107, 108, 109},
			{119, 118, 117, 116, 115, 114, 113, 112, 111, 110},
			{120, 121, 122, 123, 124, 125, 126, 127, 128, 129},
			{139, 138, 137, 136, 135, 134, 133, 132, 131, 130},
			{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
	ans = longestIncreasingPath(matrix);
	System.out.println("LongestIncreasingPath demo03 reult:" + ans);
}