Longest Increasing Path in a Matrix

You are given an m x n integer grid heights. Starting from any cell, you may repeatedly move to an adjacent cell — up, down, left, or right (no diagonal moves) — but only if the value in the cell you move to is strictly greater than the value in your current cell.

A path is the sequence of cells you visit this way, and its length is the number of cells it contains. Find the length of the longest such path that can be formed anywhere in the grid, and return that length.

Rules to keep in mind:

• You may start the path at any cell in the grid.
• Movement is restricted to the four orthogonal neighbors — diagonal steps are not allowed.
• You may only step onto a neighboring cell whose value is strictly greater than the value of your current cell (equal values break the chain).
• You do not need to visit every cell — you're only looking for the single longest strictly-increasing chain of moves available anywhere in the grid.

Examples

Example 1:

Input: heights = [[3,4,5],[2,7,6],[1,8,9]]

Output: 6

Explanation:

One longest path is 1 -> 2 -> 3 -> 4 -> 5 -> 6, following the cells (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (1,2), giving a chain of 6 cells where each step's value strictly increases and each move is to an orthogonal neighbor.

Example 2:

Input: heights = [[5,5],[5,5]]

Output: 1

Explanation:

Every cell has the same value, so no move is ever allowed (each move requires a strictly greater neighbor). The best you can do is stand on a single cell, giving a path length of 1.

Constraints

• 1 <= m, n <= 200
• 0 <= heights[i][j] <= 2^31 - 1
• m * n is at most 40000