diff options
author | Jack Sangdahl <[email protected]> | 2025-01-20 19:14:40 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-20 19:14:40 -0700 |
commit | f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840 (patch) | |
tree | f14143bbe088557d169d00c2f26b01d37dc6f952 | |
parent | 9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb (diff) | |
download | leetcode-f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840.tar.gz leetcode-f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840.zip |
2017. grid game
-rw-r--r-- | grid_game.c | 45 | ||||
-rw-r--r-- | grid_game.py | 34 |
2 files changed, 79 insertions, 0 deletions
diff --git a/grid_game.c b/grid_game.c new file mode 100644 index 0000000..1945c92 --- /dev/null +++ b/grid_game.c @@ -0,0 +1,45 @@ +// 2017. Grid Game +#include "leetcode.h" + +/* + * you are given a 0-indexed 2d array 'grid' of size '2 x n' where 'grid[r][c]' + * represents the number of points at position '[r, c]' on the matrix. two + * robots are playing a game on this matrix. both robots initially starts at + * '(0, 0)' and want to reach '(1, n - 1)'. each robot may only move to the + * right or down. at the start of the game, the first robot moves from '(0, 0)' + * to '(1, n - 1)', collecting all the points. first robot wants to minimise the + * number of points collected by the second robot. in contrast, the second robot + * wants to maximise the number of points it collects. return the number of + * points collected by the second robot + */ + +long long gridGame(int **grid, int gridSize, int *gridColSize) { + long long down = 0, up = 0; + for (int i = 0; i < gridColSize[0] - 1; i++) + down += grid[1][i]; + long long ans = down; + for (int i = gridColSize[0] - 1; i; i--) { + int cnt = fmax(down, up); + if (cnt < ans) + ans = cnt; + up += grid[0][i]; + down -= grid[1][i - 1]; + } + return up < ans ? up : ans; +} + +int main() { + int g1i[2][3] = {{2, 5, 4}, {1, 5, 1}}; + int g2i[2][3] = {{3, 3, 1}, {8, 5, 2}}; + int g3i[2][4] = {{1, 3, 1, 15}, {1, 3, 3, 1}}; + struct two_d_arr g1, g2, g3; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i); + printf("%lld\n", gridGame(g1.arr, g1.row_size, g1.col_size)); // expect: 4 + printf("%lld\n", gridGame(g2.arr, g2.row_size, g2.col_size)); // expect: 4 + printf("%lld\n", gridGame(g3.arr, g3.row_size, g3.col_size)); // expect: 7 + two_d_arr_free(&g1); + two_d_arr_free(&g2); + two_d_arr_free(&g3); +} diff --git a/grid_game.py b/grid_game.py new file mode 100644 index 0000000..ded842a --- /dev/null +++ b/grid_game.py @@ -0,0 +1,34 @@ +# 2017. Grid Game + +""" +you are given a 0-indexed 2d array 'grid' of size '2 x n' where 'grid[r][c]' +represents the number of points at position '[r, c]' on the matrix. two +robots are playing a game on this matrix. both robots initially starts at +'(0, 0)' and want to reach '(1, n - 1)'. each robot may only move to the +right or down. at the start of the game, the first robot moves from '(0, 0)' +to '(1, n - 1)', collecting all the points. first robot wants to minimise the +number of points collected by the second robot. in contrast, the second robot +wants to maximise the number of points it collects. return the number of +points collected by the second robot +""" + + +class Solution(object): + def gridGame(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + ans, up, down = float("inf"), sum(grid[0]), 0 + for i in range(len(grid[0])): + up -= grid[0][i] + ans = min(ans, max(up, down)) + down += grid[1][i] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.gridGame(grid=[[2, 5, 4], [1, 5, 1]])) + print(obj.gridGame(grid=[[3, 3, 1], [8, 5, 2]])) + print(obj.gridGame(grid=[[1, 3, 1, 15], [1, 3, 3, 1]])) |