Longest Increasing Path

Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right.

Constraints

• n, m ≤ 500 where n and m are the number of rows and columns in matrix

https://binarysearch.com/problems/Longest-Increasing-Path

Examples

Example 1

Input

• matrix =

[[1,3,5],
 [0,4,6],
 [2,2,9]]

Output

• answer = 6

Explanation

The longest path is [0, 1, 3, 5, 6, 9]

Solution