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
43
44
45
|
// 2684. Maximum Number of Moves in a Grid
#include "leetcode.h"
/*
* given a 0-indexed array 'm * n' grid consisting of positive integers. you can
* start at any cell in the first column of the matrix and traverse the grid in
* the following way: from cell '(row, col)', you can move to any of the cells:
* '(row - 1, col + 1), (row, col + 1), and (row + 1, col + 1)'. such that thhe
* value of the cell you are moving to should be strictly bigger than the value
* of the current cell. return the maximum number of moves that you can perform.
*/
int maxMoves(int **grid, int grid_size, int *grid_col_size) {
int dp[grid_size][grid_col_size[0]], max = 0;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < grid_size; i++)
dp[i][0] = 1;
for (int j = 0; j < grid_col_size[0] - 1; j++)
for (int i = 0; i < grid_size; i++) {
if (!dp[i][j])
continue;
if (i && grid[i - 1][j + 1] > grid[i][j])
dp[i - 1][j + 1] = fmax(dp[i][j] + 1, dp[i - 1][j + 1]);
if (i + 1 < grid_size && grid[i + 1][j + 1] > grid[i][j])
dp[i + 1][j + 1] = fmax(dp[i][j] + 1, dp[i + 1][j + 1]);
if (grid[i][j + 1] > grid[i][j])
dp[i][j + 1] = fmax(dp[i][j] + 1, dp[i][j + 1]);
}
for (int i = 0; i < grid_size; i++)
for (int j = 0; j < grid_col_size[i]; j++)
max = fmax(max, dp[i][j]);
return max - 1;
}
int main() {
int g1i[4][4] = {{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}};
int g2i[3][3] = {{3, 2, 4}, {2, 1, 9}, {1, 1, 7}};
struct two_d_arr g1, g2;
two_d_arr_init(&g1, 4, 4, g1i);
two_d_arr_init(&g2, 3, 3, g2i);
printf("%d\n", maxMoves(g1.arr, g1.row_size, g1.col_size)); // expect: 3
printf("%d\n", maxMoves(g2.arr, g2.row_size, g2.col_size)); // expect: 0
two_d_arr_free(&g1);
two_d_arr_free(&g2);
}
|