BFS Solution with Great Observations! Easy to Understand!
Intuition\nThe problem involves finding the minimum time to traverse a grid while respecting cell-specific time constraints. My first thought was to leverage br
# Intuition\nThe problem involves finding the minimum time to traverse a grid while respecting cell-specific time constraints. My first thought was to leverage breadth-first search (BFS) for exploring paths in a grid, as it is well-suited for shortest path problems. However, the constraints on traversal time make this problem unique. Oscillating at the starting point (0,0) until the grid becomes traversable is a clever way to handle time alignment issues, ensuring feasibility without overcomplicating the logic.\n\nBinary search on time is a natural optimization since the solution space (time) is large, and feasibility checks for each time can be efficiently performed using BFS.\n\n\n# Approach\nPre-check for Feasibility:\n\nIf there are no neighbors of (0,0) with a time constraint \u2264 1, it is impossible to start, so return -1.\nBinary Search on Time:\n\nUse binary search to minimize the time required to traverse the grid.\nFor each midpoint (mid) in the search, compute the actual time as actualMid = 2 * mid + (n + m) % 2 to handle grid parity.\nBFS for Feasibility Check:\n\nPerform BFS starting from the target cell (n-1, m-1) to check if it\'s possible to reach (0,0) with the given time.\nTrack the remaining time at each cell using a canDo array initialized to -1.\nFor each cell, traverse its neighbors if the neighbor\'s grid time is \u2264 the current cell\'s remaining time - 1.\nOscillation to Align Time:\n\nIf (0,0) is reachable before the required time, oscillate between (0,0) and its neighbors until it is feasible to proceed toward (n-1, m-1).\nResult:\n\nThe binary search returns the smallest mid where BFS confirms feasibility.\n\n\n# Complexity\n- Time complexity:\n$$O(n*m * log(1e5))$$\n\n- Space complexity:\n$$O(n*m)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n\n        // Step 1: Check if it\'s even possible to start\n        // If (0,0)\'s neighbors are not accessible with time <= 1, return -1\n        bool canStart = false;\n        for (int i = -1; i <= 1; i++) {\n            for (int j = -1; j <= 1; j++) {\n                if (abs(i) != abs(j)) { // Only consider valid neighbors (not diagonals)\n                    int nx = i, ny = j;\n                    if (nx >= 0 && nx < n && ny >= 0 && ny < m) {\n                        if (grid[nx][ny] <= 1) {\n                            canStart = true;\n                        }\n                    }\n                }\n            }\n        }\n        if (!canStart) {\n            return -1; // Early exit if no valid start path exists\n        }\n\n        // Step 2: Binary search on time\n        // We are looking for the minimum `mid` such that we can traverse the grid\n        int low = 0, high = 1e5, ans = -1;\n        while (low <= high) {\n            int mid = (low + high) >> 1;\n\n            // Convert mid to the actual time required (consider parity of grid dimensions)\n            int actualMid = 2 * mid + (n + m) % 2;\n\n            // Step 3: Feasibility test using BFS\n            if (isFeasible(grid, n, m, actualMid)) {\n                ans = actualMid; // Store the result if feasible\n                high = mid - 1;  // Search for a smaller time\n            } else {\n                low = mid + 1;   // Search for a larger time\n            }\n        }\n        return ans;\n    }\n\nprivate:\n    // Helper function to check if it\'s feasible to traverse the grid with given `time`\n    bool isFeasible(const vector<vector<int>>& grid, int n, int m, int time) {\n        if (time < grid[n - 1][m - 1]) return false; // Impossible if time < destination\'s requirement\n\n        // Initialize a 2D array to track the maximum allowable time at each cell\n        vector<vector<int>> canDo(n, vector<int>(m, -1));\n        canDo[n - 1][m - 1] = time;\n\n        // BFS initialization\n        queue<pair<int, int>> q;\n        q.push({n - 1, m - 1});\n\n        while (!q.empty()) {\n            auto [x, y] = q.front();\n            q.pop();\n\n            int pathTime = canDo[x][y]; // Current time remaining to traverse\n\n            // Explore neighbors\n            for (int i = -1; i <= 1; i++) {\n                for (int j = -1; j <= 1; j++) {\n                    if (abs(i) != abs(j)) { // Only consider valid neighbors (no diagonals)\n                        int nx = x + i, ny = y + j;\n\n                        // Check bounds and if the neighbor hasn\'t been visited\n                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && canDo[nx][ny] == -1) {\n                            // If the neighbor\'s grid time is within the remaining time\n                            if (grid[nx][ny] <= pathTime - 1) {\n                                canDo[nx][ny] = pathTime - 1; // Update allowable time for this cell\n                                q.push({nx, ny});             // Push neighbor into the queue\n                            }\n                        }\n                    }\n                }\n            }\n        }\n\n        // Check if we reached the start cell (0,0)\n        return canDo[0][0] != -1;\n    }\n};\n\n```
['Binary Search', 'Breadth-First Search', 'C++']