aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-06 22:25:43 -0600
committerJack Sangdahl <[email protected]>2025-05-06 22:25:43 -0600
commit3521f588bcb62799cd10de0acc7eb294d1a58b26 (patch)
tree3afc7b7a97982b919ece9b1055396b3ee08a138c
parent60f186c6df107c7632d37fe8bde204fb9ba54b6c (diff)
downloadleetcode-3521f588bcb62799cd10de0acc7eb294d1a58b26.tar.gz
leetcode-3521f588bcb62799cd10de0acc7eb294d1a58b26.zip
3341. find minimum time to reach last room 1
-rw-r--r--find_min_time_reach_last_room1.c85
-rw-r--r--find_min_time_reach_last_room1.py41
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]]))