Beats 100% ✅|| Waiting Time Approach || Simple Dijkstra's Algorithm || C++ || Java || Python3
Initial Check:\n\n If it\'s impossible to leave the top-left cell because the required time for the first move (grid[0][1] or grid[1][0]) is greater than 1, ret
**Initial Check:**\n\n* If it\'s impossible to leave the top-left cell because the required time for the first move (grid[0][1] or grid[1][0]) is greater than 1, return -1.\n\n**Priority Queue Setup:**\n\n* Use a priority queue (min-heap) to always explore the next cell with the smallest possible arrival time.\n* Push the starting cell (0, 0) with time 0 into the queue.\n\n**Traversal Logic:**\n\nWhile the queue is not empty:\n* Pop the cell with the minimum time from the queue.\n* Check if this cell is the bottom-right cell; if so, return the current time.\n* Mark the cell as visited to prevent revisiting.\n\n**Neighbor Exploration:**\n\nFor each adjacent cell (up, down, left, right):\n* Check if it is within bounds and not visited.\n* Calculate the minimum time to enter this cell:\n* Ensure the time is at least the required time for the cell (grid[newX][newY]).\n* Adjust the waiting time if the parity (odd/even) of the current time and the required time doesn\'t align.\n\n**Update Priority Queue:**\n\n* Push the newly calculated time and coordinates of the adjacent cell into the priority queue.\n\n**Final Case:**\n\n* If the queue is empty and the bottom-right cell hasn\'t been reached, return -1.\n\n\n\n**C++ Code**\n\n```\ntypedef pair<int, pair<int,int>> par;\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        int row = grid.size();\n        int col = grid[0].size();\n        if(min(grid[0][1], grid[1][0])>1)\n            return -1;\n        vector<vector<bool>> visited(row, vector<bool>(col));\n        queue<par> q1;\n        q1.push({0,{0,0}});\n        visited[0][0] = true;\n        vector<pair<int,int>> dirs{{0,1}, {1,0}, {0,-1}, {-1,0}};\n        while(!q1.empty()) {\n            auto curr = q1.top();\n            q1.pop();\n            int x = curr.second.first;\n            int y = curr.second.second;\n            int time = curr.first;\n            \n            if(x==row-1 && y==col-1)\n                return time;\n            \n            for(int i=0;i<4;i++) {\n                int newX = dirs[i].first + x;\n                int newY = dirs[i].second + y;\n                if(newX>=0 && newX<row && newY>=0 && !visited[newX][newY] && newY<col) {\n                    int waitingTime = 0;\n                    int diff = abs(grid[newX][newY]-time);\n                    if(!(diff&1))\n                        waitingTime = 1;\n                    int newTime = max(grid[newX][newY] + waitingTime, time+1);\n                    q1.push({newTime, {newX, newY}});\n                    visited[newX][newY] = true;\n                }\n            }\n        }\n        return -1;\n    }\n};\n```\n\n**Java Code**\n\n```\nimport java.util.*;\n\nclass Solution {\n    public int minimumTime(int[][] grid) {\n        int row = grid.length;\n        int col = grid[0].length;\n\n        if (Math.min(grid[0][1], grid[1][0]) > 1) \n            return -1;\n\n        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));\n        pq.add(new int[]{0, 0, 0});\n\n        boolean[][] visited = new boolean[row][col];\n        visited[0][0] = true;\n\n        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n\n        while (!pq.isEmpty()) {\n            int[] current = pq.poll();\n            int time = current[0];\n            int x = current[1];\n            int y = current[2];\n\n            if (x == row - 1 && y == col - 1) \n                return time;\n\n            for (int[] dir : directions) {\n                int newX = x + dir[0];\n                int newY = y + dir[1];\n\n                if (newX >= 0 && newX < row && newY >= 0 && newY < col && !visited[newX][newY]) {\n                    int waitingTime = 0;\n                    int diff = Math.abs(grid[newX][newY] - time);\n\n                    if ((diff & 1) == 0) \n                        waitingTime = 1;\n\n                    int newTime = Math.max(grid[newX][newY] + waitingTime, time + 1);\n                    pq.add(new int[]{newTime, newX, newY});\n                    visited[newX][newY] = true;\n                }\n            }\n        }\n\n        return -1;\n    }\n}\n```\n\n**Python3 Code**\n\n```\nfrom heapq import heappush, heappop\nfrom typing import List\n\nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        row, col = len(grid), len(grid[0])\n\n        if min(grid[0][1], grid[1][0]) > 1:\n            return -1\n\n        pq = []\n        heappush(pq, (0, 0, 0))\n\n        visited = [[False] * col for _ in range(row)]\n        visited[0][0] = True\n\n        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n\n        while pq:\n            time, x, y = heappop(pq)\n\n            if x == row - 1 and y == col - 1:\n                return time\n\n            for dx, dy in directions:\n                newX, newY = x + dx, y + dy\n\n                if 0 <= newX < row and 0 <= newY < col and not visited[newX][newY]:\n                    diff = abs(grid[newX][newY] - time)\n                    waitingTime = 1 if diff % 2 == 0 else 0\n                    newTime = max(grid[newX][newY] + waitingTime, time + 1)\n                    heappush(pq, (newTime, newX, newY))\n                    visited[newX][newY] = True\n\n        return -1\n```
['Breadth-First Search', 'Graph', 'C', 'Heap (Priority Queue)', 'Python', 'Java', 'Python3']