29-11-2024
\n\n# Code\ncpp []\nusing info = tuple<int, short, short>; // (time, i, j)\nconst static int d[5] = {0, 1, 0, -1, 0};\nclass Solution {\npublic:\n    inline sta
\n\n# Code\n```cpp []\nusing info = tuple<int, short, short>; // (time, i, j)\nconst static int d[5] = {0, 1, 0, -1, 0};\nclass Solution {\npublic:\n    inline static bool isOutside(short i, short j, short n, short m) {\n        return i < 0 || i >= n || j < 0 || j >= m;\n    }\n\n    int minimumTime(vector<vector<int>>& grid) {\n        if (grid[1][0]>1 && grid[0][1]>1)  return -1;// edge case\n    \n        short n = grid.size(), m = grid[0].size();\n        vector<vector<int>> time(n, vector<int>(m, INT_MAX));\n        priority_queue<info, vector<info>, greater<info>> pq;\n\n        // Start at (0, 0) with time=0 \n        pq.emplace(0, 0, 0);\n        time[0][0] = 0;\n        while (!pq.empty()) {\n            auto [t, i, j] = pq.top();\n            pq.pop();\n        //    cout<<" t="<<int(t)<<" i="<<int(i)<<" j="<<int(j)<<endl;\n            // reach the destination\n            if (i == n - 1 && j == m - 1)\n                return t;\n\n            // Traverse all four directions\n            for (int a = 0; a < 4; a++) {\n                int r = i + d[a], s = j + d[a + 1];\n                if (isOutside(r, s, n, m)) continue;\n\n                // minimum time to reach (r, s)\n                int w=((grid[r][s]-t)&1)?0:1;\n                int nextTime = max(t+1, grid[r][s]+w); // backward if neccessary\n\n                // update if this path having quicker time\n                if (nextTime < time[r][s]) {\n                    time[r][s] = nextTime;\n                    pq.emplace(nextTime, r, s);\n                }\n            }\n        }\n\n        return -1; // never reach\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['C++']