428. Fall Guys
0
Medium
In the final round of a Fall Guys match, you must navigate a square matrix of integers. Starting from any position in the first row, you can move to the block directly in front of you (b[i+1][j]), or to any of the diagonally connected blocks (b[i+1][j-1] or b[i+1][j+1]), as long as you don't fall out of the matrix. However, you cannot move within the same row (b[i][j-1] or b[i][j+1]). Your objective is to find the falling path that yields the maximum sum of all the blocks you pass through, according to the given rules and matrix.
Input Format
The first line of input contains two integers, N (number of rows) and M (number of columns) of the matrix. The next N lines contain M space-separated integers that describe the matrix.
Output Format
Print the minimum sum of any falling path through the matrix.
Example
Input
3 3
2 1 3
6 5 4
7 8 9
Output
13
Constraints
n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100
1 <= n <= 100
-100 <= matrix[i][j] <= 100
Loading...
View Submissions
Console