A mining survey grid is R-by-C, each cell holding an integer ore-grade reading. A drill can move from a cell to any of its 4 edge-adjacent neighbors (up, down, left, right), but only if the neighbor's reading is strictly greater than the current cell's reading.
A drilling path is a sequence of cells where each step follows that rule; its length is the number of cells it visits (a single cell is a valid path of length 1). Find the length of the longest possible drilling path anywhere in the grid.
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers, the ore-grade readings.
A single integer: the number of cells in the longest strictly increasing path.
Example 1
Input
3 3 9 9 4 6 6 8 2 1 1
Expected
4
Explanation
Starting from the 1 at row 2, column 1, the path 1 -> 2 -> 6 -> 9 moves to the adjacent 2 at (2,0), up to 6 at (1,0), then up to 9 at (0,0), visiting 4 cells, the longest possible.
Example 2
Input
3 3 3 4 5 3 2 6 2 2 1
Expected
4
Explanation
The path 3 -> 4 -> 5 -> 6 along the top row and down the right column visits 4 cells, the longest strictly increasing path.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →