diff options
author | Jack Sangdahl <[email protected]> | 2025-05-08 11:01:25 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-08 11:01:25 -0600 |
commit | 9b8f993a101cb3f7ab3fdb753c3956a6e9a256c2 (patch) | |
tree | 3a48128c0f5f0c00cb76eb53d4e2e1f3c7bac2f9 | |
parent | 3521f588bcb62799cd10de0acc7eb294d1a58b26 (diff) | |
download | leetcode-9b8f993a101cb3f7ab3fdb753c3956a6e9a256c2.tar.gz leetcode-9b8f993a101cb3f7ab3fdb753c3956a6e9a256c2.zip |
3342. find minimum time to reach last room 2
-rw-r--r-- | find_min_time_reach_last_room2.c | 150 | ||||
-rw-r--r-- | find_min_time_reach_last_room2.py | 43 |
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]])) |