Easy to understand || Beat 98%✅
Intuition\nThe problem is about finding the shortest time to reach the bottom-right cell of a grid while respecting the constraints on the earliest time each ce
# **Intuition**\nThe problem is about finding the shortest time to reach the bottom-right cell of a grid while respecting the constraints on the earliest time each cell can be visited. This can be solved using a **Dijkstra-like approach**, as it involves minimizing a cost (time) to reach the destination.\n\n---\n\n# **Approach**\n1. **Initial Check**: If the first move from `(0,0)` is blocked (`grid[0][1] > 1` and `grid[1][0] > 1`), return `-1`.\n2. **Priority Queue**:\n   - Use a priority queue to process cells in the order of increasing time.\n   - Each entry is `{row, col, time}`.\n3. **Time Calculation**:\n   - If the current time meets the cell\u2019s time constraint, move immediately.\n   - If not, wait until the earliest valid time, adjusting for parity:\n     - If the time difference is odd, add an extra second.\n4. **Termination**:\n   - Return the time when the bottom-right cell is reached.\n   - If no path exists, return `-1`.\n---\n\n# **Complexity**\n- **Time**: O(N\u2217M\u2217Log(N\u2217M))\n- **Space**: O(N\u2217M)\n\n\n# Code\n```java []\nclass Solution {\n    // directions {right ,top,down,left}\n    private final static int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };\n\n    public int minimumTime(int[][] grid) {\n        if (grid[0][1] > 1 && grid[1][0] > 1) // initially no move possible\n            return -1;\n        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]); // queue{row,col,time}\n        queue.offer(new int[] { 0, 0, 0 });\n        boolean[][] visited = new boolean[grid.length][grid[0].length];\n        visited[0][0] = true;\n        while (!queue.isEmpty()) {\n            int[] cell = queue.poll();\n            for (int[] direction : directions) {\n                int nx = cell[0] + direction[0];\n                int ny = cell[1] + direction[1];\n                int currentTime = cell[2];\n                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !visited[nx][ny]) {\n                    int time = grid[nx][ny] - currentTime; // time difference b/w curr time and grid time to move\n                    if (time == 1) {\n                        time = grid[nx][ny];\n                    } else if (time <= 0) {\n                        time = currentTime + 1;\n                    } else {\n                        time = Math.max(grid[nx][ny], currentTime) + (time % 2 == 0 ? 1 : 0);\n                    }\n                    if (nx == grid.length - 1 && ny == grid[0].length - 1)\n                        return time;\n                    queue.offer(new int[] { nx, ny, time });\n                    visited[nx][ny] = true;\n                }\n            }\n        }\n        return -1;\n    }\n```\n```c++ []\nusing namespace std;\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n        // Directions for moving in 4 directions: right, down, left, up\n        vector<array<int, 2>> directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };\n        // If the first move is blocked, return -1\n        if (grid[0][1] > 1 && grid[1][0] > 1) \n            return -1;\n        // Priority queue for Dijkstra-like traversal (min-heap): {time, row, col}\n        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;\n        pq.push({0, 0, 0}); // Start from the top-left corner at time 0\n        // Visited array to avoid revisiting cells\n        vector<vector<bool>> visited(n, vector<bool>(m, false));\n        visited[0][0] = true;\n        while (!pq.empty()) {\n            auto [currentTime, x, y] = pq.top();\n            pq.pop();\n            // Explore all neighbors\n            for (auto [dx, dy] : directions) {\n                int nx = x + dx, ny = y + dy;\n                // Check if the neighbor is within bounds and not visited\n                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {\n                    int time = grid[nx][ny] - currentTime; // Time difference to satisfy the grid condition\n                    if (time == 1) {\n                        time = grid[nx][ny];\n                    } else if (time <= 0) {\n                        time = currentTime + 1;\n                    } else {\n                        time = max(grid[nx][ny], currentTime) + (time % 2 == 0 ? 1 : 0);\n                    }\n                    // If we reach the bottom-right cell, return the time\n                    if (nx == n - 1 && ny == m - 1)\n                        return time;\n                    // Mark the neighbor as visited and add it to the priority queue\n                    pq.push({time, nx, ny});\n                    visited[nx][ny] = true;\n                }\n            }\n        }\n        // If the bottom-right cell is not reachable, return -1\n        return -1;\n    }\n};\n```\n
['Java']