aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-20 19:14:40 -0700
committerJack Sangdahl <[email protected]>2025-01-20 19:14:40 -0700
commitf4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840 (patch)
treef14143bbe088557d169d00c2f26b01d37dc6f952
parent9a4b43e0c4e6ae790fad4e1c51bbc3b31f3490cb (diff)
downloadleetcode-f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840.tar.gz
leetcode-f4f6e23ad8b1f3aafee8562f9a3f64a3a76a5840.zip
2017. grid game
-rw-r--r--grid_game.c45
-rw-r--r--grid_game.py34
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]]))