[C++, Java, Python] 🏓 Ping Pong Dijkstra
\n# Intuition\nWe want to find minimum time to reach bottom right cell. We\'ll have to traverse the matrix as the time in each cell allows. We can use a priorit
\n# Intuition\nWe want to find minimum time to reach bottom right cell. We\'ll have to traverse the matrix as the time in each cell allows. We can use a priority queue to keep track of time.\nSome things to keep in mind:\n1. If we can not move to the neighboring cells from starting position we can not move anywhere in the matrix hence answer is -1. \n2. But if we can move to the neighboring cells from starting position, we can move anywhere in the matrix. We can wait by playing "ping pong" between previous cell and current cell till a neighboring cell opens up.\n\n\n# Approach\n* If `grid[0][1] > 1 and grid[1][0] > 1` we can not move anywhere from cell `grid[0][0]` hence answer is `-1`\n* Use priority queue to find next cell with minimum time to move to it\n* If time for a neighbor (target) cell is > 1 + time for current cell. We can not directly move to target cell. We will have to "ping pong" between previous cell and current cell. When playing ping pong between previous and current cell there can be two cases. \n    * Let\'s say time for target cell is 4 and current time is 2, difference = 2 (even).\n        * Move to prev cell, time = 3\n        * Move to curr cell, time = 4\n        * Move to target cell, time = 5. \n        * Hence we reach target cell with time: **target cell time + 1** when difference between target cell time and curr cell time is even.\n    * Let\'s say time for target cell is 5 and current time is 2, difference = 3 (odd).\n        * Move to prev cell, time = 3\n        * Move to curr cell, time = 4\n        * Move to target cell, time = 5. \n        * Hence we reach target cell with time: target cell time when difference between target cell time and curr cell time is odd.\n    * This "ping pong" is captured in the `wait` variable in the code\n\n\n# Complexity\n- Time complexity: `O(mnlog(mn))`\n\n- Space complexity: `O(mn)`\n\n# Code\n**Python3**:\n```\ndef minimumTime(self, grid: List[List[int]]) -> int:\n    if grid[0][1] > 1 and grid[1][0] > 1: return -1\n    m, n = len(grid), len(grid[0])\n    visited = set()\n    pq = [(grid[0][0], 0, 0)]\n    \n    while pq:\n        time, row, col = heappop(pq)\n        if row == m-1 and col == n-1: return time\n        if (row, col) in visited: continue\n        visited.add((row, col))\n        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n            r, c = row + dr, col + dc\n            if 0 <= r < m and 0 <= c < n and (r, c) not in visited:\n                wait = 1 if ((grid[r][c] - time) % 2 == 0) else 0\n                heappush(pq, (max(time + 1, grid[r][c] + wait), r, c))\n```\n\n**C++**\n```\nint minimumTime(vector<vector<int>>& grid) {\n    // Check if the starting points are blocked\n    if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n    \n    int m = grid.size(), n = grid[0].size();\n    vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n    vector<vector<bool>> visited(m, vector<bool>(n, false));\n    priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;\n    \n    pq.push({grid[0][0], 0, 0}); // Start at top-left corner\n    while (!pq.empty()) {\n        // Get the current time, row, and column\n        int time = pq.top()[0], row = pq.top()[1], col = pq.top()[2];\n        pq.pop();\n        \n        // Check if we\'ve reached the bottom-right corner\n        if (row == m - 1 && col == n - 1) return time;\n        \n        // Mark the current cell as visited\n        if (visited[row][col]) continue;\n        visited[row][col] = true;\n        \n        // Explore the neighboring cells\n        for (auto dr: dirs) {\n            int r = row + dr[0], c = col + dr[1];\n            if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) continue;\n            \n            // Calculate the time required to reach the neighboring cell\n            int wait = (grid[r][c] - time) % 2 == 0;\n            pq.push({max(grid[r][c] + wait, time + 1), r, c});\n        }\n    }\n    return -1; // We couldn\'t reach the bottom-right corner. \n               // We will never actually encounter this in practice.\n}\n```\n\n**Java**:\n```\npublic int minimumTime(int[][] grid) {\n    if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n    \n    int m = grid.length, n = grid[0].length;\n    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n    boolean[][] visited = new boolean[m][n];\n    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));\n    pq.offer(new int[]{grid[0][0], 0, 0});\n    \n    while (!pq.isEmpty()) {\n        int[] curr = pq.poll();\n        int time = curr[0], row = curr[1], col = curr[2];\n        \n        if (row == m - 1 && col == n - 1) return time;\n        if (visited[row][col]) continue;\n        visited[row][col] = true;\n        \n        for (int[] dir : dirs) {\n            int r = row + dir[0], c = col + dir[1];\n            if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) continue;\n            int wait = ((grid[r][c] - time) % 2 == 0) ? 1 : 0;\n            pq.offer(new int[]{Math.max(grid[r][c] + wait, time + 1), r, c});\n        }\n    }\n    return -1;\n}\n```
['C++', 'Java', 'Python3']