778. 水位上升的泳池中游泳

搜索

• 从终点开始，将与终点接触，并且值小于终点的点纳入终点区域范围
• 查找与终点区域范围相接的最小值，将终点值设为该最小值，并扩展终点范围
• 直到终点范围包括起点
• 正着搜索也是同样的道理，需要遍历所有时间，因此可以使用二分查找优化

class Solution {
  public:
    int n;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    bool dfs(vector<vector<int>>& grid, int cur) {
        queue<pair<int, int>> q;
        bool vis[64][64] = {false};
        vis[0][0] = true;
        q.push({0, 0});
        while(q.size() > 0) {
            auto it = q.front();
            if (it.first == n - 1 && it.second == n - 1) return true;
            q.pop();
            for (int i = 0; i < 4; i ++) {
                int x = it.first + dir[i][0];
                int y = it.second + dir[i][1];
                if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && grid[x][y] <= cur) {
                    vis[x][y] = true;
                    q.push({x, y});
                }
            }
        }
        return false;
    }
    int swimInWater(vector<vector<int>>& grid) {
        int time_left = grid[0][0];
        int time_right = 0;

        n = grid.size();
        
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                time_right = max(time_right, grid[i][j]);
            }
        }

        while (time_left < time_right) {
            int time_middle = (time_left + time_right) >> 1;
            if (dfs(grid, time_middle)) {
                time_right = time_middle;
            } else {
                time_left = time_middle + 1;
            }
        }
        return time_left;
    }
};

38/38 cases passed (20 ms)
Your runtime beats 57.40 % of cpp submissions
Your memory usage beats 43.19 % of cpp submissions (10.13 MB)