diff options
author | Jack Sangdahl <[email protected]> | 2025-05-06 22:25:43 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-06 22:25:43 -0600 |
commit | 3521f588bcb62799cd10de0acc7eb294d1a58b26 (patch) | |
tree | 3afc7b7a97982b919ece9b1055396b3ee08a138c | |
parent | 60f186c6df107c7632d37fe8bde204fb9ba54b6c (diff) | |
download | leetcode-3521f588bcb62799cd10de0acc7eb294d1a58b26.tar.gz leetcode-3521f588bcb62799cd10de0acc7eb294d1a58b26.zip |
3341. find minimum time to reach last room 1
-rw-r--r-- | find_min_time_reach_last_room1.c | 85 | ||||
-rw-r--r-- | find_min_time_reach_last_room1.py | 41 |
2 files changed, 126 insertions, 0 deletions
diff --git a/find_min_time_reach_last_room1.c b/find_min_time_reach_last_room1.c new file mode 100644 index 0000000..e632ae4 --- /dev/null +++ b/find_min_time_reach_last_room1.c @@ -0,0 +1,85 @@ +// 3341. Find Minimum Time to Reach Last Room I +#include "leetcode.h" + +/* + * there is a dungeo with 'n x m' rooms arranged as a grid. you are given a 2d + * array 'moveTime' of size 'n x m' where 'moveTime[i][j]' represents the + * minimum time in seconds when you can start moving to that room. you start + * from the room at '(0, 0)' at time 't = 0' and can move to an adjacent room. + * moving between adjacent rooms takes exactly one second. return the minimum + * time to reach the room 'n - 1, m - 1'. + */ + +int minTimeToReach(int **moveTime, int moveTimeSize, int *moveTimeColSize) { + int n = moveTimeSize, m = moveTimeColSize[0]; + if (!n) + return -1; + int total = n * m, *dp = (int *)malloc(total * sizeof(int)); + for (int i = 0; i < total; i++) + dp[i] = INT_MAX; + dp[0] = 0; + int *heap = (int *)malloc(total * sizeof(int)), hsize = 0; + heap[hsize++] = 0; + int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; + while (hsize) { + int u = heap[0]; + heap[0] = heap[--hsize]; + int i = 0; + while (1) { + int l = 2 * i + 1, r = 2 * i + 2, best = i; + if (l < hsize && dp[heap[l]] < dp[heap[best]]) + best = l; + if (r < hsize && dp[heap[r]] < dp[heap[best]]) + best = r; + if (best == i) + break; + int tmp = heap[i]; + heap[i] = heap[best]; + heap[best] = tmp; + i = best; + } + if (u == total - 1) + break; + int t = dp[u], x = u / m, y = u % m; + for (int d = 0; d < 4; d++) { + int nx = x + dirs[d][0], ny = y + dirs[d][1]; + if (nx < 0 || nx >= n || ny < 0 || ny >= m) + continue; + int idx = nx * m + ny; + int w = (moveTime[nx][ny] > t ? moveTime[nx][ny] : t) + 1; + if (w < dp[idx]) { + dp[idx] = w; + int j = hsize; + heap[hsize++] = idx; + while (j > 0 && dp[heap[j]] < dp[heap[(j - 1) / 2]]) { + int p = (j - 1) / 2, tmp = heap[j]; + heap[j] = heap[p]; + heap[p] = tmp; + j = p; + } + } + } + } + int ans = dp[total - 1]; + free(dp); + free(heap); + return ans; +} + +int main() { + int mt1i[2][2] = {{0, 4}, {4, 4}}, mt2i[2][3] = {{0, 0, 0}, {0, 0, 0}}, + mt3i[2][2] = {{0, 1}, {1, 2}}; + struct two_d_arr mt1, mt2, mt3; + two_d_arr_init(&mt1, ARRAY_SIZE(mt1i), ARRAY_SIZE(mt1i[0]), mt1i); + two_d_arr_init(&mt2, ARRAY_SIZE(mt2i), ARRAY_SIZE(mt2i[0]), mt2i); + two_d_arr_init(&mt3, ARRAY_SIZE(mt3i), ARRAY_SIZE(mt3i[0]), mt3i); + printf("%d\n", + minTimeToReach(mt1.arr, mt1.row_size, mt1.col_size)); // expect: 6 + printf("%d\n", + minTimeToReach(mt2.arr, mt2.row_size, mt2.col_size)); // expect: 3 + printf("%d\n", + minTimeToReach(mt3.arr, mt3.row_size, mt3.col_size)); // expect: 3 + two_d_arr_free(&mt1); + two_d_arr_free(&mt2); + two_d_arr_free(&mt3); +} diff --git a/find_min_time_reach_last_room1.py b/find_min_time_reach_last_room1.py new file mode 100644 index 0000000..3ce1848 --- /dev/null +++ b/find_min_time_reach_last_room1.py @@ -0,0 +1,41 @@ +# 3341. Find Minimum Time to Reach Last Room I +import heapq + +""" +there is a dungeo with 'n x m' rooms arranged as a grid. you are given a 2d +array 'moveTime' of size 'n x m' where 'moveTime[i][j]' represents the +minimum time in seconds when you can start moving to that room. you start +from the room at '(0, 0)' at time 't = 0' and can move to an anyacent room. +moving between anyacent rooms takes exactly one second. return the minimum +time to reach the room 'n - 1, m - 1'. +""" + + +class Solution(object): + def minTimeToReach(self, moveTime): + """ + :type moveTime: List[List[int]] + :rtype: int + """ + n, m = len(moveTime), len(moveTime[0]) + dp = [["inf"] * m for i in range(n)] + h = [[0, 1, 0, 0]] + moveTime[0][0] = -1 + while h: + t, c, i, j = heapq.heappop(h) + if t >= dp[i][j]: + continue + if i == n - 1 and j == m - 1: + return t + dp[i][j] = t + for nx, ny in [[1, 0], [0, 1], [-1, 0], [0, -1]]: + x, y = i + nx, j + ny + if 0 <= x < n and 0 <= y < m and dp[x][y] == "inf": + heapq.heappush(h, [max(moveTime[x][y] + c, t + c), 2 - c, x, y]) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minTimeToReach(moveTime=[[0, 4], [4, 4]])) + print(obj.minTimeToReach(moveTime=[[0, 0, 0], [0, 0, 0]])) + print(obj.minTimeToReach(moveTime=[[0, 1], [1, 2]])) |