821. Fall Guys
0
Medium
In the final round of a Fall Guys match, you must navigate through a square matrix of size n * n. 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 blocks diagonally connected to your current block (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]) or you will fall. Your objective is to find the falling path that results in the maximum sum of all the blocks you pass through, according to the given rules and matrix.
Input Format
The first line of input consists of 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