当前位置：首页 > article >正文

Leetcode 778 Swim in a Rising water

article 2024/11/15 6:15:05

题是指什么时候你能从左上角游到右下角。第t分钟的时候，水的高度是t。grid[i][j]是海拔，只有当前水的高度没过海拔，我才能游。你可以往四个方向游泳。求问，最少第几分钟我能从左上角游到右下角（有一条路径）
从本质上是要求找到一个最小的h，使得从左上角走到右下角能游完
解题思路：二分答案，h的范围肯定是grid[0][0]，到grid中的最大值，取定一个h，看能不能游完

bfs求解

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int l = 0, r = 0;
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                r = max(r, grid[i][j]);
            }
        }

        while (l < r) {
            int mid = l + (r - l) / 2;
            if(bfs(mid, grid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    using PII = pair<int, int>;
    bool bfs(int h, vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        queue<PII> q;
        int dk[] = {-1, 0, 1, 0, -1};
        if(grid[0][0] > h) {
            return false;
        }
        q.push({0,0});
        vector<vector<int>> vis(m, vector<int>(n, 0));
        vis[0][0] = true;
        while(q.size()) {
            auto node = q.front();
            q.pop();
            int x = node.first;
            int y = node.second;
            if(x == m - 1 && y == n - 1) {
                return true;
            } 
            for(int i = 0; i < 4; i++) {
                int nx = x + dk[i];
                int ny = y + dk[i+1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && grid[nx][ny] <= h) {
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        return false;
    }

};

dfs求解

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int l = 0, r = 0;
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                r = max(r, grid[i][j]);
            }
        }

        while (l < r) {
            int mid = l + (r - l) / 2;
            vector<vector<int>> vis(m, vector<int>(n, 0));
            if(dfs(0, 0, mid, vis, grid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    bool dfs(int x, int y, int h, vector<vector<int>>& vis, vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        if(grid[x][y] > h) {
            return false;
        }
        if(x == m - 1 && y == n - 1) {
            return true;
        }
        vis[x][y] = 1;
        int dk[] = {-1, 0, 1, 0, -1};
        for(int i = 0; i < 4; i++) {
            int dx = x + dk[i];
            int dy = y + dk[i+1];
            if(dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && dfs(dx, dy, h, vis, grid)) {
                return true;
            } 
        }
        return false;
    }


};