Longest Increasing Path in a Grid

Given a square grid of integers, find the length of the longest increasing path in the grid. From any cell, you may move to one of the four adjacent cells: up, down, left, or right. A path is defined as a sequence of cells where each subsequent cell has a strictly greater value than its predecessor. Use an efficient algorithm (e.g., DFS with memoization) to determine the longest increasing path.

The movement condition can be formally expressed using LaTeX as follows:

$$ grid[i][j] < grid[k][l] $$

for any two adjacent cells \((i,j)\) and \((k,l)\).

inputFormat

The input is given via standard input (stdin). The first line contains an integer \( n \) representing the size of the grid. If \( n > 0 \), each of the next \( n \) lines contains \( n \) space-separated integers denoting the grid's row values. If \( n = 0 \), the grid is empty.

outputFormat

Output a single integer via standard output (stdout), which is the length of the longest increasing path found in the grid.

3
9 9 4
6 6 8
2 1 1

4