Java with Dijkstra's Algorithm Approach
Intuition\nThe problem is essentially about finding the shortest path from the top-left corner to the bottom-right corner of a grid. The challenge lies in the f
# Intuition\nThe problem is essentially about finding the shortest path from the top-left corner to the bottom-right corner of a grid. The challenge lies in the fact that the grid values impose constraints on when each cell can be accessed. This hints at a Dijkstra-like approach where we prioritize the earliest possible time to reach each cell.\n\n# Approach\n1. **Initial Feasibility Check**: If the immediate neighbors of the starting cell are inaccessible, it\'s impossible to proceed, so return `-1`.\n2. **Dijkstra\'s Algorithm**: Use a priority queue to explore cells in increasing order of the time required to reach them.\n3. **Transition Rules**:\n   - For each neighboring cell, calculate the earliest possible time it can be reached, accounting for the parity (even/odd nature of time relative to the grid value).\n   - Update the minimum time to reach the neighbor if this new time is better.\n4. **Termination**: If the bottom-right corner is reached, return the time. If the queue is exhausted and the target hasn\'t been reached, return `-1`.\n\n# Complexity\n- **Time Complexity**: \n  $$O(m \\cdot n \\cdot \\log(m \\cdot n))$$, where \\(m\\) and \\(n\\) are the dimensions of the grid. Each cell is processed once, and operations on the priority queue are logarithmic in the number of elements.\n- **Space Complexity**:\n  $$O(m \\cdot n)$$ for the `minTimeToReach` array and the priority queue.\n\n# Code\n```java\nclass Solution {\n    public int minimumTime(int[][] grid) {\n        int rows = grid.length, cols = grid[0].length;\n\n        if (Math.min(grid[0][1], grid[1][0]) > 1) {\n            return -1;\n        }\n\n        int[][] minTimeToReach = new int[rows][cols];\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                minTimeToReach[i][j] = Integer.MAX_VALUE;\n            }\n        }\n        minTimeToReach[0][0] = 0;\n\n        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));\n        priorityQueue.offer(new int[]{0, 0, 0});\n\n        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n\n        while (!priorityQueue.isEmpty()) {\n            int[] current = priorityQueue.poll();\n            int currentTime = current[0], currentRow = current[1], currentCol = current[2];\n\n            if (currentRow == rows - 1 && currentCol == cols - 1) {\n                return currentTime;\n            }\n\n            if (currentTime != minTimeToReach[currentRow][currentCol]) {\n                continue;\n            }\n\n            for (int[] direction : directions) {\n                int newRow = currentRow + direction[0], newCol = currentCol + direction[1];\n                if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) {\n                    continue;\n                }\n\n                int newTime = Math.max(currentTime + 1, grid[newRow][newCol] + 1 - (grid[newRow][newCol] - currentTime) % 2);\n                if (newTime >= minTimeToReach[newRow][newCol]) {\n                    continue;\n                }\n\n                minTimeToReach[newRow][newCol] = newTime;\n                priorityQueue.offer(new int[]{newTime, newRow, newCol});\n            }\n        }\n\n        return -1;\n    }\n}\n```
['Java']