blob: 128fb856fd51d55b9837b60619c03d205fd55dd5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
// 1289. Minimum Falling Path Sum II
#include "leetcode.h"
/*
* given a 'n * n' integer matrix 'grid' return the minimum sum of a falling
* path with non zero shifts. a falling path with non zero shifts is a choice of
* exactly one element from each row of 'grid' such that no two elements chosen
* in adjacent rows are in the same column
*/
int min(int **grid, int gridSize, int *gridColSize, int curr) {
int min = INT_MAX;
for (int i = 0; i < curr; i++)
if (min > grid[gridSize][i])
min = grid[gridSize][i];
for (int i = curr + 1; i < *gridColSize; i++)
if (min > grid[gridSize][i])
min = grid[gridSize][i];
return min;
}
int minFallingPathSum(int **grid, int gridSize, int *gridColSize) {
int **list = (int **)malloc(sizeof(int *) * 2);
list[0] = malloc(sizeof(int) * *gridColSize);
list[1] = malloc(sizeof(int) * *gridColSize);
gridSize--;
int k = gridSize % 2;
for (int i = 0; i < *gridColSize; i++)
list[k][i] = grid[gridSize][i];
gridSize--;
int other = k;
while (gridSize >= 0) {
k = gridSize % 2;
for (int i = 0; i < *gridColSize; i++)
list[k][i] = min(list, other, gridColSize, i) + grid[gridSize][i];
other = k;
gridSize--;
}
int ans = min(list, 0, gridColSize, *gridColSize);
free(list[0]), free(list[1]), free(list);
return ans;
}
|