Classic Dijkstra II

For this problem (and the #3342), all we need to do is apply classic Dijkstra, there is only one tiny adjustment for the "weight" based on the time, everything else is standard. Code is down below, cheers, ACC.

Find Minimum Time to Reach Last Room I - LeetCode

3341. Find Minimum Time to Reach Last Room I

Medium

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 exactly one second.

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: 6

Explanation:

The minimum time required is 6 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 one second.

Example 2:

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

Output: 3

Explanation:

The minimum time required is 3 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 one second.
• At time t == 2, move from room (1, 1) to room (1, 2) in one second.

Example 3:

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

Output: 3

 

Constraints:

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

Accepted

10,575

Submissions

36,837

public class Solution {
    public class StartTimeCell
    {
        public int row = 0;
        public int col = 0;
        public int time = 0;
        public int key = 0;

        public StartTimeCell(int row, int col, int time)
        {
            this.row = row;
            this.col = col;
            this.time = time;

            this.key = row * 55 + col;
        }
    }

    public int MinTimeToReach(int[][] moveTime)
    {
        PriorityQueue pQueue = new PriorityQueue(true, 1000);
        HashSet visited = new HashSet();

        StartTimeCell stc = new StartTimeCell(0, 0, 0);
        visited.Add(stc.key);
        pQueue.Enqueue(stc, stc.time);

        while (pQueue.Count > 0)
        {
            double priority = 0;
            StartTimeCell currentCell = (StartTimeCell)pQueue.Dequeue(out priority);

            if (currentCell.row == moveTime.Length - 1 &&
                currentCell.col == moveTime[0].Length - 1)
            {
                return currentCell.time;
            }

            int[] rowDelta = { 1, -1, 0, 0 };
            int[] colDelta = { 0, 0, 1, -1 };

            for (int i = 0; i < rowDelta.Length; i++)
            {
                int row = currentCell.row + rowDelta[i];
                int col = currentCell.col + colDelta[i];

                if (row >= 0 &&
                    row < moveTime.Length &&
                    col >= 0 &&
                    col < moveTime[row].Length)
                {
                    int startTime = (currentCell.time >= moveTime[row][col]) ? currentCell.time : moveTime[row][col];
                    StartTimeCell nextCell = new StartTimeCell(row, col, startTime + 1);

                    if (!visited.Contains(nextCell.key))
                    {
                        visited.Add(nextCell.key);
                        pQueue.Enqueue(nextCell, nextCell.time);
                    }
                }
            }
        }

        return -1; //should never get here, btw
    }
}

public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private double priority;
        public HeapEntry(object item, double priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public double Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private bool ascend;
    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue(bool ascend, int cap = -1)
    {
        capacity = 10000000;
        if (cap > 0) capacity = cap;
        heap = new HeapEntry[capacity];
        this.ascend = ascend;
    }

    public object Dequeue(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }
    public object Peak(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public object Peak(/*out double priority*/)
    {
        //priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public void Enqueue(object item, double priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        if (this.ascend)
        {
            while ((index > 0) && (heap[parent].Priority > he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
        else
        {
            while ((index > 0) && (heap[parent].Priority < he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (this.ascend)
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority > heap[child + 1].Priority))
                {
                    child++;
                }
            }
            else
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority < heap[child + 1].Priority))
                {
                    child++;
                }
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}