Longest Increasing Path in a Matrix

Problem Statement

Given an m x n matrix of integers, return the length of the longest strictly increasing path.

From each cell, you can move in four directions: up, down, left, right. You cannot go outside the matrix or move to a cell with equal or smaller value.

Input Format

Line 1: Number of rows. Following lines: Space-separated integers for each row.

Output Format

Length of the longest increasing path.

Examples

Example 1:

Input:
[[9,9,4],
 [6,6,8],
 [2,1,1]]

Output: 4

Longest path: 1 -> 2 -> 6 -> 9