You are given an n by n grid of integers. A falling path starts at any cell in the top row. From a cell in row i, column j it moves to row i+1 at column j-1, j, or j+1 (staying inside the grid). The path ends when it leaves the bottom row.
Return the minimum possible sum of all cells visited by such a path.
Line 1: an integer n.
Next n lines: each has n space-separated integers.
A single integer: the minimum falling-path sum (it may be negative).
Example 1
Input
3 2 1 3 6 5 4 7 8 9
Expected
13
Explanation
The path 1 (top middle) -> 4 -> 8 sums to 13, which is the smallest reachable falling-path sum.
Example 2
Input
1 -5
Expected
-5
Explanation
A 1x1 grid has a single cell, so the only falling path has sum -5.
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 →