aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-08 11:01:25 -0600
committerJack Sangdahl <[email protected]>2025-05-08 11:01:25 -0600
commit9b8f993a101cb3f7ab3fdb753c3956a6e9a256c2 (patch)
tree3a48128c0f5f0c00cb76eb53d4e2e1f3c7bac2f9
parent3521f588bcb62799cd10de0acc7eb294d1a58b26 (diff)
downloadleetcode-9b8f993a101cb3f7ab3fdb753c3956a6e9a256c2.tar.gz
leetcode-9b8f993a101cb3f7ab3fdb753c3956a6e9a256c2.zip
3342. find minimum time to reach last room 2
-rw-r--r--find_min_time_reach_last_room2.c150
-rw-r--r--find_min_time_reach_last_room2.py43
2 files changed, 193 insertions, 0 deletions
diff --git a/find_min_time_reach_last_room2.c b/find_min_time_reach_last_room2.c
new file mode 100644
index 0000000..a81e83a
--- /dev/null
+++ b/find_min_time_reach_last_room2.c
@@ -0,0 +1,150 @@
+// 3342. Find Minimum Time to Reach Last Room II
+#include "leetcode.h"
+
+/*
+ * there is a dungeon 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 '(0, 0)' at time 't = 0' and can move to an adjacent room.
+ * moving between adjacent rooms takes one second for one move and two seconds
+ * for the next, alternating between the two. return the minimum time to reach
+ * the room '(n - 1, m - 1)'.
+ */
+
+#define VIS 0x80000000
+#define MASK 0x7FFFFFFF
+
+struct grid {
+ int row;
+ int col;
+};
+
+void heap_down(struct grid *start, struct grid *end, struct grid *curr,
+ int **moveTime) {
+ struct grid *child = 1 + start + ((curr - start) << 1);
+ if (child <= end) {
+ if (child < end) {
+ struct grid *next = child + 1;
+ if ((MASK & moveTime[child->row][child->col]) <
+ (MASK & moveTime[curr->row][curr->col]))
+ child++;
+ }
+ if ((MASK & moveTime[child->row][child->col]) <
+ (MASK & moveTime[curr->row][curr->col])) {
+ child->col ^= curr->col;
+ curr->col ^= child->col;
+ child->col ^= curr->col;
+ child->row ^= curr->row;
+ curr->row ^= child->row;
+ child->row ^= curr->row;
+ heap_down(start, end, child, moveTime);
+ }
+ }
+}
+
+void heap_up(struct grid *start, struct grid *curr, int **moveTime) {
+ if (start < curr) {
+ struct grid *parent = start + ((curr - 1 - start) >> 1);
+ if ((MASK & moveTime[curr->row][curr->col]) <
+ (MASK & moveTime[parent->row][parent->col])) {
+ curr->col ^= parent->col;
+ parent->col ^= curr->col;
+ curr->col ^= parent->col;
+ curr->row ^= parent->row;
+ parent->row ^= curr->row;
+ curr->row ^= parent->row;
+ heap_up(start, parent, moveTime);
+ }
+ }
+}
+
+int minTimeToReach(int **moveTime, int moveTimeSize, int *moveTimeColSize) {
+ struct grid ast[moveTimeSize * (*moveTimeColSize)], *pst = ast;
+ pst->col = 0;
+ (pst++)->row = 0;
+ moveTime[0][0] = VIS;
+ int ans = 0;
+ int n = moveTimeSize - 1, m = *moveTimeColSize - 1;
+ while (ast < pst) {
+ char move = (ast->col + ast->row) % 2 ? 2 : 1;
+ int time = MASK & moveTime[ast->row][ast->col];
+ if (ast->row) {
+ int next = ast->row - 1, *curr = ast->col + moveTime[next];
+ if (0 <= *curr) {
+ if (time > *curr)
+ *curr = time;
+ *curr += move;
+ *curr |= VIS;
+ pst->col = ast->col;
+ pst->row = next;
+ heap_up(ast, pst++, moveTime);
+ }
+ }
+ if (ast->col) {
+ int next = ast->col - 1, *curr = next + moveTime[ast->row];
+ if (0 <= *curr) {
+ if (time > *curr)
+ *curr = time;
+ *curr += move;
+ *curr |= VIS;
+ pst->col = next;
+ pst->row = ast->row;
+ heap_up(ast, pst++, moveTime);
+ }
+ }
+ if (m > ast->col) {
+ int next = ast->col + 1, *curr = next + moveTime[ast->row];
+ if (0 <= *curr) {
+ if (time > *curr)
+ *curr = time;
+ *curr += move;
+ if (m == next && n == ast->row) {
+ ans = *curr;
+ break;
+ }
+ *curr |= VIS;
+ pst->col = next;
+ pst->row = ast->row;
+ heap_up(ast, pst++, moveTime);
+ }
+ }
+ if (n > ast->row) {
+ int next = ast->row + 1, *curr = ast->col + moveTime[next];
+ if (0 <= *curr) {
+ if (time > *curr)
+ *curr = time;
+ *curr += move;
+ if (n == next && m == ast->col) {
+ ans = *curr;
+ break;
+ }
+ *curr |= VIS;
+ pst->col = ast->col;
+ pst->row = next;
+ heap_up(ast, pst++, moveTime);
+ }
+ }
+ ast->col = (--pst)->col;
+ ast->row = pst->row;
+ heap_down(ast, pst - 1, ast, moveTime);
+ }
+ return ans;
+}
+
+int main() {
+ int mt1i[2][2] = {{0, 4}, {4, 4}}, mt2i[2][4] = {{0, 0, 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: 7
+ printf("%d\n",
+ minTimeToReach(mt2.arr, mt2.row_size, mt2.col_size)); // expect: 6
+ printf("%d\n",
+ minTimeToReach(mt3.arr, mt3.row_size, mt3.col_size)); // expect: 4
+ two_d_arr_free(&mt1);
+ two_d_arr_free(&mt2);
+ two_d_arr_free(&mt3);
+}
diff --git a/find_min_time_reach_last_room2.py b/find_min_time_reach_last_room2.py
new file mode 100644
index 0000000..11bf407
--- /dev/null
+++ b/find_min_time_reach_last_room2.py
@@ -0,0 +1,43 @@
+# 3342. Find Minimum Time to Reach Last Room II
+import heapq
+
+"""
+there is a dungeon 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 '(0, 0)' at time 't = 0' and can move to an adjacent room.
+moving between adjacent rooms takes one second for one move and two seconds
+for the next, alternating between the two. 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)]
+ heap = [[0, 0, 0]]
+ moveTime[0][0] = -1
+ while heap:
+ t, i, j = heapq.heappop(heap)
+ if t >= dp[i][j]:
+ continue
+ if i == n - 1 and j == m - 1:
+ return t
+ dp[i][j] = t
+ for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
+ x, y = i + di, j + dj
+ c = (i + j) % 2 + 1
+ if 0 <= x < n and 0 <= y < m and dp[x][y] == "inf":
+ heapq.heappush(heap, [max(moveTime[x][y], t) + 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, 0, 0]]))
+ print(obj.minTimeToReach(moveTime=[[0, 1], [1, 2]]))