Longest Increasing Path in a Matrix in Go

You get a grid of numbers, matrix, with m rows and n columns.

Return the number of cells on the longest increasing path in the grid.

A path can start in any cell. Each step moves to the next cell up, down, left or right. It can't move diagonally or leave the grid.

In an increasing path, each step goes to a bigger number. Equal numbers don't count as bigger.

The grid is an array of rows. Each row is an array of numbers.

Example 1:

Input: matrix = [
  [1, 2, 3],
  [8, 9, 4],
  [7, 6, 5]
]
Output: 9
Explanation: Start at 1 and walk around the edge:
1, 2, 3, 4, 5, 6, 7, 8.
Then step into the middle, to 9.
The path uses all 9 cells.

Example 2:

Input: matrix = [
  [1, 2, 2, 3]
]
Output: 2
Explanation: The two 2s are next to each other.
A path can't step from one to the other.
So the longest paths are 1 → 2 and 2 → 3.

Example 3:

Input: matrix = [
  [9, 8],
  [2, 7]
]
Output: 4
Explanation: The path is 2 → 7 → 8 → 9.
It moves right, then up, then left.

Constraints:

• 1 to 200 rows.
• 1 to 200 columns.
• Each number is a whole number from 0 to 1,000,000,000.
• The longest increasing path has at most 1,000 cells.