Constest - 3/11/2024 || Q-3 || BFS || Heap
Approach\n\n1. Modeling the Problem:\n   - Each cell in the grid represents a point that can be traversed, with a cost associated with moving into that cell def
### Approach\n\n1. **Modeling the Problem**:\n   - Each cell in the grid represents a point that can be traversed, with a cost associated with moving into that cell defined by the `moveTime` array.\n   - The objective is to minimize the time taken to reach the cell at `(n-1, m-1)` starting from `(0, 0)`.\n\n2. **Data Structure**:\n   - A priority queue (min-heap) is used to explore the cell with the minimum time first. This is crucial for Dijkstra-like algorithms to ensure that once a cell\'s minimum time is finalized, it is not updated again.\n\n3. **Pair Class**:\n   - The `Pair` class holds the information about the current cell\'s coordinates (`row`, `col`), the accumulated time (`time`), and an additional field (`which`) to determine the increment added to the time in the next steps.\n\n4. **Initialization**:\n   - The `minTime` 2D array is initialized to store the minimum time to reach each cell, starting with `Long.MAX_VALUE` to indicate that all cells are initially unreachable except the starting cell which is set to `0`.\n\n5. **Traversal Logic**:\n   - The algorithm processes cells by expanding to their neighbors (up, down, left, right).\n   - For each neighbor, it calculates the new time based on the current time and the value in the `moveTime` grid.\n   - If the new calculated time is less than the stored time for that neighbor, it updates the `minTime` for that cell and adds it to the priority queue for further exploration.\n\n6. **Termination**:\n   - If the algorithm reaches the target cell `(n-1, m-1)`, it returns the time taken to reach there. If the queue is exhausted without reaching the target, it returns `-1`, indicating that the target is unreachable.\n\n### Intuition\n\nThe core intuition behind the algorithm is to always expand the least costly option available (in terms of time) to ensure the shortest path to the target. By using a priority queue, the algorithm efficiently picks the next cell to explore based on the least accumulated time, mimicking the behavior of breadth-first search with a cost metric.\n\n### Time Complexity\n\n- **Time Complexity**: The complexity is \\(O((n*m) \\log(n * m))\\), where \\(n\\) is the number of rows and \\(m\\) is the number of columns. This arises because:\n  - Each cell (total of \\(n * m\\)) may be added to the priority queue at most once.\n  - The `offer` operation on the priority queue takes \\(O(log k)\\) time, where \\(k\\) is the number of elements in the queue.\n\n### Space Complexity\n\n- **Space Complexity**: The space complexity is \\(O(n * m)\\) for storing the `minTime` array and the priority queue that may potentially hold all cells in the worst case.\n\n### Summary\n\nThis approach efficiently finds the minimum time to traverse a grid while considering the movement cost defined by the `moveTime` array. The use of a priority queue ensures optimal selection of paths, which is key in pathfinding algorithms like Dijkstra\'s. The code structure is clean and modular, making it easy to understand and maintain.\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    class Pair implements Comparable<Pair> {\n        int row;\n        int col;\n        long time;\n        int which;\n\n        Pair(int r, int c, long t,int w) {\n            this.row = r;\n            this.col = c;\n            this.time = t;\n            this.which = w;\n        }\n\n        @Override\n        public int compareTo(Pair other) {\n            return Long.compare(this.time, other.time);\n        }\n    }\n\n    public int minTimeToReach(int[][] moveTime) {\n        int n = moveTime.length;\n        int m = moveTime[0].length;\n\n        // Priority queue for minimum time expansion (Dijkstra-like)\n        PriorityQueue<Pair> pq = new PriorityQueue<>();\n        pq.offer(new Pair(0, 0, 0L,-1));\n\n        // Minimum time to reach each cell, initialized to a large number\n        long[][] minTime = new long[n][m];\n        for (int i = 0; i < n; i++) {\n            Arrays.fill(minTime[i], Long.MAX_VALUE);\n        }\n        minTime[0][0] = 0L;\n\n        // Direction vectors for moving up, down, left, right\n        int[] dx = {0, 0, 1, -1};\n        int[] dy = {1, -1, 0, 0};\n\n        while (!pq.isEmpty()) {\n            Pair current = pq.poll();\n            int r = current.row, c = current.col;\n            long t = current.time;\n             int add = (current.which==1?2:1);\n\n            // If we reached the target cell, return the minimum time (converted to int)\n            if (r == n - 1 && c == m - 1) return (int) t;\n\n            // Explore neighbors\n            for (int i = 0; i < 4; i++) {\n                int rr = r + dx[i];\n                int cc = c + dy[i];\n\n                if (rr >= 0 && rr < n && cc >= 0 && cc < m) {\n                    long newTime = Math.max(t + add, (long)(moveTime[rr][cc]+add));\n\n                    // Only add to queue if it\'s an improvement\n                    if (minTime[rr][cc] > newTime) {\n                        minTime[rr][cc] = newTime;\n                        pq.offer(new Pair(rr, cc, newTime,add));\n                    }\n                }\n            }\n        }\n\n        return -1; // If unreachable (edge case)\n    }\n}\n\n\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Java']