778: Swim-in-Rising-Water
Hard

table of contents

You can simply just run a breadth-first search starting from grid[0][0]. Everytime, you stumble upon a new square, you can mark it as seen in the seen matrix, and update its value in grid if the current square is smaller. We can then place the new square into a min heap, sorted based on its water level, and repeat until seen.back.back == 1.

code

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
        vector<vector<int>> seen (m, vector<int>(n, 0));
        seen[0][0] = 1;
        pq.push({grid[0][0], {0, 0}});

        while(seen.back().back() == 0) {
            auto top = pq.top();
            pq.pop();
    
            for (int i = 0; i < 4; ++i) {
                int X = top.second.first;
                int Y = top.second.second;
                int newX = X + direction[i][0];
                int newY = Y + direction[i][1];

                if (newX >= 0 && newY >= 0 && newX < m && newY < n && seen[newX][newY] == 0) {
                    grid[newX][newY] = max(grid[newX][newY], grid[X][Y]);
                    pq.push({grid[newX][newY], {newX, newY}});
                    seen[newX][newY] = 1;
                }
            }
        }

        return grid.back().back();
    }
private:
    vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
};

complexity

time taken