[Java/C++/Python] Priority Queue
Intuition\nUse priority queue.\n\n\n# Explanation\nThe key is [t, c, i, j],\nwhere it takes t seconds to arrive (i, j),\nthe next move will cost c seconds.\n\nU
# **Intuition**\nUse priority queue.\n<br>\n\n# **Explanation**\nThe key is `[t, c, i, j]`,\nwhere it takes `t` seconds to arrive `(i, j)`,\nthe next move will cost `c` seconds.\n\nUse `3 - d` to determine the next cost of move.\n<br>\n\n# **Complexity**\nTime `O(mnlogmn)`\nSpace `O(mn)`\n<br>\n\n```Java [Java]\n    public int minTimeToReach(int[][] A) {\n        int n = A.length, m = A[0].length, inf = Integer.MAX_VALUE;\n        int[][] dp = new int[n][m];\n        for (int i = 0; i < n; i++) {\n            Arrays.fill(dp[i], inf);\n        }\n        PriorityQueue<int[]> h = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));\n        h.offer(new int[]{0, 0, 0}); // arrive time, i, j\n        A[0][0] = -1;\n\n        while (!h.isEmpty()) {\n            int[] cur = h.poll();\n            int t = cur[0], i = cur[1], j = cur[2];\n            if (t >= dp[i][j]) continue;\n            if (i == n - 1 && j == m - 1) return t;\n            dp[i][j] = t;\n\n            int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};\n            for (int[] dir : dirs) {\n                int x = i + dir[0], y = j + dir[1], c = (i + j) % 2 + 1;\n                if (0 <= x && x < n && 0 <= y && y < m && dp[x][y] == inf) {\n                    h.offer(new int[]{Math.max(A[x][y], t) + c, x, y});\n                }\n            }\n        }\n        return -1;\n    }\n```\n\n```C++ [C++]\n    int minTimeToReach(vector<vector<int>>& A) {\n        int n = A.size(), m = A[0].size(), inf = INT_MAX;\n        vector<vector<int>> dp(n, vector<int>(m, inf));\n        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> h;\n        h.push({0, 0, 0}); // arrive time, i, j\n        A[0][0] = -1;\n\n        vector<vector<int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};\n        while (!h.empty()) {\n            vector<int> cur = h.top();\n            h.pop();\n            int t = cur[0], i = cur[1], j = cur[2];\n            if (t >= dp[i][j]) continue;\n            if (i == n - 1 && j == m - 1) return t;\n            dp[i][j] = t;\n\n            for (auto& dir : dirs) {\n                int x = i + dir[0], y = j + dir[1], c = (i + j) % 2 + 1;\n                if (0 <= x && x < n && 0 <= y && y < m && dp[x][y] == inf) {\n                    h.push({max(A[x][y], t) + c, x, y});\n                }\n            }\n        }\n        return -1;\n    }\n```\n\n```py [Python3]\n    def minTimeToReach(self, A: List[List[int]]) -> int:\n        n, m = len(A), len(A[0])\n        dp = [[inf] * m for i in range(n)]\n        h = [[0, 0, 0]] # arrive time, i, j\n        A[0][0] = -1\n        while h:\n            t, i, j = heappop(h)\n            if t >= dp[i][j]: continue\n            if i == n - 1 and j == m - 1: return t\n            dp[i][j] = t\n            for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:\n                x, y = i + di, j + dj\n                c = (i + j) % 2 + 1\n                if 0 <= x < n and 0 <= y < m and dp[x][y] == inf:\n                    heappush(h, [max(A[x][y], t) + c, x, y])\n```\n
[]