Longest Increasing Path

Given an m x n integer matrix, find the length of the longest path such that for every pair of consecutive cells in the path, the value is strictly increasing. From each cell you may move in one of four directions: up, down, left, or right. You may not move diagonally or move outside the matrix boundary.

Example 1

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

Output: 4 — the path 1 -> 2 -> 6 -> 9 (bottom-left column upward).

Example 2

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

Output: 4 — the path 3 -> 4 -> 5 -> 6.

Constraints

• 1 <= rows, cols <= 200
• 0 <= matrix[i][j] <= 2^31 - 1