diff options
author | Jack Sangdahl <[email protected]> | 2025-01-17 19:10:05 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-17 19:10:05 -0700 |
commit | 3a737ea8dc8304354f75257b3f796e507354ccdc (patch) | |
tree | 5bdc6d1c20cfc507af864387d63ab76731538a08 | |
parent | 88de92a17bb68635921e1625d5b3063e26ea9c03 (diff) | |
download | leetcode-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.c | 111 | ||||
-rw-r--r-- | min_cost_valid_path.py | 44 |
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]])) |