Swim in Rising Water

Problem

You are given a square 2-D matrix of distinct integers grid where each integer grid[i][j] represents the elevation at position (i, j).

Rain starts to fall at time = 0, which causes the water level to rise. At time t, the water level across the entire grid is t.

You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time t.

Starting from the top left square (0, 0), return the minimum amount of time it will take until it is possible to reach the bottom right square (n - 1, n - 1).

Examples

Example 1:

Input: grid = [[0,1],[2,3]]

Output: 3

Explanation: For a path to exist to the bottom right square grid[1][1] the water elevation must be at least 3. At time t = 3, the water level is 3.

Example 2:

Input: grid = [
  [0,1,2,10],
  [9,14,4,13],
  [12,3,8,15],
  [11,5,7,6]
]

Output: 8

Explanation: The water level must be at least 8 to reach the bottom right square. The path is [0, 1, 2, 4, 8, 7, 6].

Constraints

• grid.length == grid[i].length
• 1 <= grid.length <= 50
• 0 <= grid[i][j] < n^2

You should aim for a solution with O((n^2)logn) time and O(n^2) space, where n is the number of rows or columns of the square matrix.

Solution

We run BFS, where we are optimizing for the time. We can move between cells with 0 cost, so long as the heights are less than or equal to the time.

class Solution {
    inline static constexpr std::array<std::pair<int, int>, 5> OFFSETS = {{
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    }};
    struct Node {
        int r;
        int c;
        int t;
    };
 
public:
    int swimInWater(vector<vector<int>>& grid) {
        const int ROWS = grid.size();
        const int COLS = grid[0].size();
 
        auto cmp = [](const Node& a, const Node& b) {
            return a.t > b.t; // min-heap by time
        };
 
        std::priority_queue<Node, std::vector<Node>, decltype(cmp)> open(cmp);
        std::unordered_set<int> closed;
        open.emplace(0, 0, grid[0][0]);
 
        while (!open.empty()) {
            auto current = open.top();
            open.pop();
            
            // Previously visited
            if (closed.contains(current.r * COLS + current.c)) {
                continue;
            }
            closed.insert(current.r * COLS + current.c);
 
            // Solution
            if (current.r == ROWS - 1 && current.c == COLS - 1) {
                return current.t;
            }
            for (const auto &[dr, dc] : OFFSETS) {
                int rr = current.r + dr;
                int cc = current.c + dc;
                // Out of bounds
                if (rr < 0 || cc < 0 || rr >= ROWS || cc >= COLS) { continue; }
                int next_time = std::max(current.t, grid[rr][cc]);
                open.emplace(rr, cc, next_time);
            }
        }
        return -1;
    }
};