[LeetCode][JavaScript]Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

---

寻找最长的递增路径，返回长度。

DFS递归遍历找出最长的路径，开一个哈希表记录已经访问过的节点，提高效率。

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {
    var direction = [{x : -1, y : 0}, {x : 1, y : 0}, {x : 0, y : -1}, {x : 0, y : 1}];
    var dictionary = {}, max = 0;
    for(var i = 0; i < matrix.length; i++)
        for(var j = 0; j < matrix[i].length; j++)
            max = Math.max(max, dfs(i, j));
    return max;
    
    function dfs(x, y){
        var curr = dictionary[x + '#' + y];
        if(curr) return curr;
        curr = matrix[x][y];
        
        var d, max = 0, isEnd = true, tmp;
        for(var i = 0; i < direction.length; i++){
            d = direction[i];
            if(matrix[x + d.x]){
                tmp = matrix[x + d.x][y + d.y];
                if(tmp && tmp > curr){
                    max = Math.max(max, dfs(x + d.x, y + d.y));
                    isEnd = false;
                }
            }
        }
        
        max = isEnd ? 1 : max + 1;
        dictionary[x + '#' + y] = max;
        return max;
    }
}