3342. Find Minimum Time to Reach Last Room II

Description

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).

Two rooms are adjacent if they share a common wall, either horizontally or vertically.

 

Example 1:

Input: moveTime = [[0,4],[4,4]]

Output: 7

Explanation:

The minimum time required is 7 seconds.

• At time t == 4, move from room (0, 0) to room (1, 0) in one second.
• At time t == 5, move from room (1, 0) to room (1, 1) in two seconds.

Example 2:

Input: moveTime = [[0,0,0,0],[0,0,0,0]]

Output: 6

Explanation:

The minimum time required is 6 seconds.

• At time t == 0, move from room (0, 0) to room (1, 0) in one second.
• At time t == 1, move from room (1, 0) to room (1, 1) in two seconds.
• At time t == 3, move from room (1, 1) to room (1, 2) in one second.
• At time t == 4, move from room (1, 2) to room (1, 3) in two seconds.

Example 3:

Input: moveTime = [[0,1],[1,2]]

Output: 4

 

Constraints:

• 2 <= n == moveTime.length <= 750
• 2 <= m == moveTime[i].length <= 750
• 0 <= moveTime[i][j] <= 109

Solutions

Solution 1: Dijkstra's Algorithm

We define a two-dimensional array $\textit{dist}$, where $\textit{dist}[i][j]$ represents the minimum time required to reach room $(i, j)$ from the starting point. Initially, we set all elements in the $\textit{dist}$ array to infinity, and then set the $\textit{dist}$ value of the starting point $(0, 0)$ to $0$.

We use a priority queue $\textit{pq}$ to store each state, where each state consists of three values $(d, i, j)$, representing the time $d$ required to reach room $(i, j)$ from the starting point. Initially, we add the starting point $(0, 0, 0)$ to $\textit{pq}$.

In each iteration, we take the front element $(d, i, j)$ from $\textit{pq}$. If $(i, j)$ is the endpoint, we return $d$. If $d$ is greater than $\textit{dist}[i][j]$, we skip this state. Otherwise, we enumerate the four adjacent positions $(x, y)$ of $(i, j)$. If $(x, y)$ is within the map, we calculate the final time $t$ from $(i, j)$ to $(x, y)$ as $t = \max(\textit{moveTime}[x][y], \textit{dist}[i][j]) + (i + j) \bmod 2 + 1$. If $t$ is less than $\textit{dist}[x][y]$, we update the value of $\textit{dist}[x][y]$ and add $(t, x, y)$ to $\textit{pq}$.

The time complexity is $O(n \times m \times \log (n \times m))$, and the space complexity is $O(n \times m)$. Here, $n$ and $m$ are the number of rows and columns of the map, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        dist = [[inf] * m for _ in range(n)]
        dist[0][0] = 0
        pq = [(0, 0, 0)]
        dirs = (-1, 0, 1, 0, -1)
        while 1:
            d, i, j = heappop(pq)
            if i == n - 1 and j == m - 1:
                return d
            if d > dist[i][j]:
                continue
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < n and 0 <= y < m:
                    t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1
                    if dist[x][y] > t:
                        dist[x][y] = t
                        heappush(pq, (t, x, y))

class Solution {
    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;
        int[][] dist = new int[n][m];
        for (var row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[0][0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[] {0, 0, 0});
        int[] dirs = {-1, 0, 1, 0, -1};
        while (true) {
            int[] p = pq.poll();
            int d = p[0], i = p[1], j = p[2];

            if (i == n - 1 && j == m - 1) {
                return d;
            }
            if (d > dist[i][j]) {
                continue;
            }

            for (int k = 0; k < 4; k++) {
                int x = i + dirs[k];
                int y = j + dirs[k + 1];
                if (x >= 0 && x < n && y >= 0 && y < m) {
                    int t = Math.max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1;
                    if (dist[x][y] > t) {
                        dist[x][y] = t;
                        pq.offer(new int[] {t, x, y});
                    }
                }
            }
        }
    }
}

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size();
        int m = moveTime[0].size();
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        dist[0][0] = 0;
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
        pq.push({0, 0, 0});
        int dirs[5] = {-1, 0, 1, 0, -1};

        while (1) {
            auto [d, i, j] = pq.top();
            pq.pop();

            if (i == n - 1 && j == m - 1) {
                return d;
            }
            if (d > dist[i][j]) {
                continue;
            }

            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k];
                int y = j + dirs[k + 1];

                if (x >= 0 && x < n && y >= 0 && y < m) {
                    int t = max(moveTime[x][y], dist[i][j]) + (i + j) % 2 + 1;
                    if (dist[x][y] > t) {
                        dist[x][y] = t;
                        pq.push({t, x, y});
                    }
                }
            }
        }
    }
};

func minTimeToReach(moveTime [][]int) int {
    n, m := len(moveTime), len(moveTime[0])
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, m)
        for j := range dist[i] {
            dist[i][j] = math.MaxInt32
        }
    }
    dist[0][0] = 0

    pq := &hp{}
    heap.Init(pq)
    heap.Push(pq, tuple{0, 0, 0})

    dirs := []int{-1, 0, 1, 0, -1}
    for {
        p := heap.Pop(pq).(tuple)
        d, i, j := p.dis, p.x, p.y

        if i == n-1 && j == m-1 {
            return d
        }
        if d > dist[i][j] {
            continue
        }

        for k := 0; k < 4; k++ {
            x, y := i+dirs[k], j+dirs[k+1]
            if x >= 0 && x < n && y >= 0 && y < m {
                t := max(moveTime[x][y], dist[i][j]) + (i+j)%2 + 1
                if dist[x][y] > t {
                    dist[x][y] = t
                    heap.Push(pq, tuple{t, x, y})
                }
            }
        }
    }
}

type tuple struct{ dis, x, y int }
type hp []tuple

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v any)      { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

function minTimeToReach(moveTime: number[][]): number {
    const [n, m] = [moveTime.length, moveTime[0].length];
    const dist: number[][] = Array.from({ length: n }, () => Array(m).fill(Infinity));
    dist[0][0] = 0;
    const pq = new PriorityQueue({ compare: (a, b) => a[0] - b[0] });
    pq.enqueue([0, 0, 0]);
    const dirs = [-1, 0, 1, 0, -1];
    while (1) {
        const [d, i, j] = pq.dequeue();
        if (i === n - 1 && j === m - 1) {
            return d;
        }
        if (d > dist[i][j]) {
            continue;
        }
        for (let k = 0; k < 4; ++k) {
            const [x, y] = [i + dirs[k], j + dirs[k + 1]];
            if (x >= 0 && x < n && y >= 0 && y < m) {
                const t = Math.max(moveTime[x][y], dist[i][j]) + ((i + j) % 2) + 1;
                if (dist[x][y] > t) {
                    dist[x][y] = t;
                    pq.enqueue([t, x, y]);
                }
            }
        }
    }
}

Comments