aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-28 22:26:31 -0600
committerJack Sangdahl <[email protected]>2024-10-28 22:26:31 -0600
commit7559cb9c4ca06e6d2dad7b5353faf23fa1852004 (patch)
tree401b11a032e158a127fdf4b05b423a564978dad6
parent6f48fe464b740f4bf8d680d70ce784467a1e3d9c (diff)
downloadleetcode-7559cb9c4ca06e6d2dad7b5353faf23fa1852004.tar.gz
leetcode-7559cb9c4ca06e6d2dad7b5353faf23fa1852004.zip
2684. maximum number of moves in a grid
-rw-r--r--max_num_moves_grid.c58
-rw-r--r--max_num_moves_grid.py43
2 files changed, 70 insertions, 31 deletions
diff --git a/max_num_moves_grid.c b/max_num_moves_grid.c
index 3b8ddfc..617135c 100644
--- a/max_num_moves_grid.c
+++ b/max_num_moves_grid.c
@@ -10,40 +10,36 @@
* of the current cell. return the maximum number of moves that you can perform.
*/
-// int dfs(int **dp, int **grid, int row_size, int *col_size, int row, int col,
-// int prev, int ith) {
-int dfs(int **dp, int r, int c, int grid[r][c], int row_size, int *col_size,
- int row, int col, int prev, int ith) {
- if (row < 0 || row >= row_size || col < 0 || col > *col_size - 1 ||
- grid[row][col] <= prev)
- return ith;
- if (dp[row][col])
- return ith + dp[row][col] + 1;
- int tmp = dfs(dp, r, c, grid, row_size, col_size, row - 1, col + 1,
- grid[row][col], ith + 1);
- tmp = fmax(tmp, dfs(dp, r, c, grid, row_size, col_size, row, col + 1,
- grid[row][col], ith + 1));
- tmp = fmax(tmp, dfs(dp, r, c, grid, row_size, col_size, row + 1, col,
- grid[row][col], ith + 1));
- dp[row][col] = tmp - ith - 1;
- return tmp;
-}
-
-// int maxMoves(int **grid, int grid_size, int *grid_col_size) {
-int maxMoves(int r, int c, int grid[r][c], int grid_size, int *grid_col_size) {
- int ans = 0;
- int **dp = malloc(sizeof(int *) * grid_size);
+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] = calloc(*grid_col_size, sizeof(int));
+ 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++)
- ans = fmax(ans, dfs(dp, r, c, grid, grid_size, grid_col_size, i, 0, 0, -1));
- return ans;
+ for (int j = 0; j < grid_col_size[i]; j++)
+ max = fmax(max, dp[i][j]);
+ return max - 1;
}
int main() {
- int g1[4][4] = {{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}};
- int g2[3][3] = {{3, 2, 4}, {2, 1, 9}, {1, 1, 7}};
- int gcs1[] = {}, gcs2[] = {};
- printf("%d\n", maxMoves(4, 4, g1, 4, gcs1)); // expect: 3
- printf("%d\n", maxMoves(3, 3, g2, 3, gcs2)); // expect: 0
+ 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);
}
diff --git a/max_num_moves_grid.py b/max_num_moves_grid.py
new file mode 100644
index 0000000..cfce8b7
--- /dev/null
+++ b/max_num_moves_grid.py
@@ -0,0 +1,43 @@
+# 2684. Maximum Number of Moves in a Grid
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def maxMoves(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ m, n, ans = len(grid), len(grid[0]), 0
+ dp = [0] * m
+ for j in range(1, n):
+ left_top, found = 0, False
+ for i in range(m):
+ next_left_top, curr = dp[i], -1
+ if i - 1 >= 0 and left_top != -1 and grid[i][j] > grid[i - 1][j - 1]:
+ curr = max(curr, left_top + 1)
+ if dp[i] != -1 and grid[i][j] > grid[i][j - 1]:
+ curr = max(curr, dp[i] + 1)
+ dp[i] = curr
+ found = found or (dp[i] != -1)
+ left_top = next_left_top
+ if not found:
+ break
+ ans = j
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxMoves(grid=[[2, 4, 3, 5], [5, 4, 9, 3], [3, 4, 2, 11], [10, 9, 13, 15]])
+ )
+ print(obj.maxMoves(grid=[[3, 2, 4], [2, 1, 9], [1, 1, 7]]))