aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-17 19:10:05 -0700
committerJack Sangdahl <[email protected]>2025-01-17 19:10:05 -0700
commit3a737ea8dc8304354f75257b3f796e507354ccdc (patch)
tree5bdc6d1c20cfc507af864387d63ab76731538a08
parent88de92a17bb68635921e1625d5b3063e26ea9c03 (diff)
downloadleetcode-3a737ea8dc8304354f75257b3f796e507354ccdc.tar.gz
leetcode-3a737ea8dc8304354f75257b3f796e507354ccdc.zip
1368. minimum cost to make at least one valid path in a grid
-rw-r--r--min_cost_valid_path.c111
-rw-r--r--min_cost_valid_path.py44
2 files changed, 155 insertions, 0 deletions
diff --git a/min_cost_valid_path.c b/min_cost_valid_path.c
new file mode 100644
index 0000000..b11562a
--- /dev/null
+++ b/min_cost_valid_path.c
@@ -0,0 +1,111 @@
+// 1368. Minimum Cost to Make at Least One Valid Path in a Grid
+#include "leetcode.h"
+
+/*
+ * given an 'm x n' grid. each cell of the grid has a sign pointing to the next
+ * cell you shhould visit if you are currently in this cell. notice that there
+ * could be some signs on the cells of the grid that point outside the grid. you
+ * will initially start at the upper left cell '(0, 0)'. a valid path in the
+ * grid is a path that starts from the uppper left cell '(0, 0)' and ends at the
+ * bbbottom right cell '(m - 1, n - 1)' following the signs on the grid. the
+ * valid path does not have to bbe the shortest. return the minimum cost to make
+ * the grid have at least one valid path
+ */
+
+struct node {
+ int state[2];
+ int moves;
+};
+
+struct queue {
+ struct node data[10000];
+ int front, rear;
+};
+
+void queue_init(struct queue *obj) {
+ obj->front = -1;
+ obj->rear = -1;
+}
+
+bool queue_empty(struct queue *obj) {
+ return obj->front == -1 && obj->rear == -1;
+}
+
+void queue_push(struct queue *obj, int *state, int moves) {
+ if (queue_empty(obj)) {
+ obj->front = 0;
+ obj->rear = 0;
+ } else
+ obj->rear = (obj->rear + 1) % 10000;
+ obj->data[obj->rear].state[0] = state[0];
+ obj->data[obj->rear].state[1] = state[1];
+ obj->data[obj->rear].moves = moves;
+}
+
+struct node queue_pop(struct queue *obj) {
+ struct node n = obj->data[obj->front];
+ if (obj->front == obj->rear) {
+ obj->front = -1;
+ obj->rear = -1;
+ } else
+ obj->front = (obj->front + 1) % 10000;
+ return n;
+}
+
+int minCost(int **grid, int gridSize, int *gridColSize) {
+ int n = gridSize, m = *gridColSize, min = INT_MAX;
+ int vis[100][100] = {0};
+ int **dp = (int **)malloc((n + 1) * sizeof(int *));
+ for (int i = 0; i < n + 1; i++)
+ dp[i] = (int *)malloc((m + 1) * sizeof(int));
+ for (int i = 0; i < n + 1; i++)
+ for (int j = 0; j < m + 1; j++)
+ dp[i][j] = -1;
+ struct queue q;
+ queue_init(&q);
+ int init_state[2] = {0, 0};
+ queue_push(&q, init_state, 0);
+ dp[0][0] = 0;
+ while (!queue_empty(&q)) {
+ struct node curr = queue_pop(&q);
+ int x = curr.state[0], y = curr.state[1];
+ int dir[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
+ for (int i = 1; i < 5; i++) {
+ int curr_move = 0, next[2];
+ if (grid[x][y] != i)
+ curr_move = 1;
+ next[0] = x + dir[i][0];
+ next[1] = y + dir[i][1];
+ int next_move = curr.moves + curr_move;
+ if (next[0] == n && next[1] == m && min < next_move)
+ min = next_move;
+ if (next[0] >= 0 && next[1] >= 0 && next[0] < n && next[1] < m &&
+ (!vis[next[0]][next[1]] || dp[next[0]][next[1]] > next_move)) {
+ dp[next[0]][next[1]] = next_move;
+ vis[next[0]][next[1]] = 1;
+ queue_push(&q, next, next_move);
+ }
+ }
+ }
+ int ans = dp[n - 1][m - 1];
+ for (int i = 0; i < n + 1; i++)
+ free(dp[i]);
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int g1i[4][4] = {{1, 1, 1, 1}, {2, 2, 2, 2}, {1, 1, 1, 1}, {2, 2, 2, 2}};
+ int g2i[3][3] = {{1, 1, 3}, {3, 2, 2}, {1, 1, 4}};
+ int g3i[2][2] = {{1, 2}, {4, 3}};
+ 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("%d\n", minCost(g1.arr, g1.row_size, g1.col_size)); // expect: 3
+ printf("%d\n", minCost(g2.arr, g2.row_size, g2.col_size)); // expect: 0
+ printf("%d\n", minCost(g3.arr, g3.row_size, g3.col_size)); // expect: 1
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&g3);
+}
diff --git a/min_cost_valid_path.py b/min_cost_valid_path.py
new file mode 100644
index 0000000..713ec86
--- /dev/null
+++ b/min_cost_valid_path.py
@@ -0,0 +1,44 @@
+# 1368. Minimum Cost to Make at Least One Valid Path in a Grid
+
+"""
+given an 'm x n' grid. each cell of the grid has a sign pointing to the next
+cell you shhould visit if you are currently in this cell. notice that there
+could be some signs on the cells of the grid that point outside the grid. you
+will initially start at the upper left cell '(0, 0)'. a valid path in the
+grid is a path that starts from the uppper left cell '(0, 0)' and ends at the
+bbbottom right cell '(m - 1, n - 1)' following the signs on the grid. the
+valid path does not have to bbe the shortest. return the minimum cost to make
+the grid have at least one valid path
+"""
+
+
+class Solution(object):
+ def minCost(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ n, m, inf, k = len(grid), len(grid[0]), 10**9, 0
+ dp, bfs = [[inf] * m for i in range(n)], []
+ dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
+
+ def dfs(x, y):
+ if not (0 <= x < n and 0 <= y < m and dp[x][y] == inf):
+ return
+ dp[x][y] = k
+ bfs.append([x, y])
+ dfs(x + dir[grid[x][y] - 1][0], y + dir[grid[x][y] - 1][1])
+
+ dfs(0, 0)
+ while bfs:
+ k += 1
+ bfs, bfs2 = [], bfs
+ [dfs(x + i, y + j) for x, y in bfs2 for i, j in dir]
+ return dp[-1][-1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCost(grid=[[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]))
+ print(obj.minCost(grid=[[1, 1, 3], [3, 2, 2], [1, 1, 4]]))
+ print(obj.minCost(grid=[[1, 2], [4, 3]]))