Longest Increasing Path in a Matrix

Description

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:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution(javascript)

/* eslint-disable no-loop-func */
/*
 * @lc app=leetcode id=329 lang=javascript
 *
 * [329] Longest Increasing Path in a Matrix
 */

// @lc code=start
/** NOTE 这题是计算最长路径
 * @param {number[][]} matrix
 * @return {number}
 */
const longestIncreasingPath = function (matrix) {
  const distance = matrix.map(items => items.map(() => 1))
  const visited = matrix.map(items => items.map(() => false))
  const dfs = (row, column, prevValue) => {
    if (
      row < 0 || row > matrix.length - 1 || column < 0 || column > matrix[0].length - 1
      || matrix[row][column] <= prevValue
    ) {
      return 0
    }
    if (visited[row][column]) {
      return distance[row][column]
    }
    visited[row][column] = true
    const value = matrix[row][column]
    distance[row][column] = Math.max(
      dfs(row, column + 1, value),
      dfs(row, column - 1, value),
      dfs(row + 1, column, value),
      dfs(row - 1, column, value),
    ) + 1
    return distance[row][column]
  }
  let max = 0
  for (let row = 0; row < matrix.length; row++) {
    for (let column = 0; column < matrix[row].length; column++) {
      max = Math.max(dfs(row, column), max)
    }
  }

  return max
}