diff options
author | Jack Sangdahl <[email protected]> | 2024-10-28 22:26:31 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-28 22:26:31 -0600 |
commit | 7559cb9c4ca06e6d2dad7b5353faf23fa1852004 (patch) | |
tree | 401b11a032e158a127fdf4b05b423a564978dad6 | |
parent | 6f48fe464b740f4bf8d680d70ce784467a1e3d9c (diff) | |
download | leetcode-7559cb9c4ca06e6d2dad7b5353faf23fa1852004.tar.gz leetcode-7559cb9c4ca06e6d2dad7b5353faf23fa1852004.zip |
2684. maximum number of moves in a grid
-rw-r--r-- | max_num_moves_grid.c | 58 | ||||
-rw-r--r-- | max_num_moves_grid.py | 43 |
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]])) |