Back 'n' Forth Dijkstra
Good ol\' Dijkstra once you work out the details.\n\nFirst of all, if the required time for both g[0][1] and g[1][0] is greater than one, we cannot move (return
Good ol\' Dijkstra once you work out the details.\n\nFirst of all, if the required time for both `g[0][1]` and `g[1][0]` is greater than one, we cannot move (return `-1`).\n\nOtherwise, we can always reach the bottom-right cell. If the current time (plus 1) is less than required, we can "wait" till the required time.\n\n> We do not wait, of course - instead, we put the required time into the priority queue. \n\nNote that we may need to add `1` to the required time, as we advance the current time in the increments of `2` seconds (by going back and forth). \n\n> For example, if the current time is `3`, and the required time is 9, we can get back to the current cell at `5`, `7`, and `9` seconds, so arrive at the adjacent cell at tenth second.\n\nFinally, we need to use "visited" matrix (`vis`) to track the shortest time to arrive at each cell.\n\n**C++**\n```cpp\nint dir[5] = {0, 1, 0, -1, 0};\nint minimumTime(vector<vector<int>>& g) {\n    int m = g.size(), n = g[0].size();\n    if (min(g[0][1], g[1][0]) > 1)\n        return -1;\n    vector<vector<int>> vis(m, vector<int>(n, INT_MAX));\n    priority_queue<array<int, 3>> pq;\n    pq.push({0, 0, 0});\n    while(!pq.empty()) {\n        auto [neg_sec, i, j] = pq.top(); pq.pop();\n        if (i == m - 1 && j == n - 1)\n            break;\n        for (int d = 0; d < 4; ++d) {\n            int x = i + dir[d], y = j + dir[d + 1];\n            if (min(x, y) >= 0 && x < m && y < n) {\n                int sec = -neg_sec + 1;\n                if (sec < g[x][y])\n                    sec = g[x][y] + (g[x][y] - sec) % 2;\n                if (sec < vis[x][y]) {\n                    vis[x][y] = sec;\n                    pq.push({-sec, x, y});\n                }\n            }\n        }\n    }\n    return vis.back().back();\n}\n```
['C']