Islands and Treasure

Problem

You are given a m×nm×n 2D grid initialized with these three possible values:

1. -1 - A water cell that can not be traversed.
2. 0 - A treasure chest.
3. INF - A land cell that can be traversed. We use the integer 2^31 - 1 = 2147483647 to represent INF.

Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest then the value should remain INF.

Assume the grid can only be traversed up, down, left, or right.

Modify the grid in-place.

Examples

Example 1:

Input: [
  [2147483647,-1,0,2147483647],
  [2147483647,2147483647,2147483647,-1],
  [2147483647,-1,2147483647,-1],
  [0,-1,2147483647,2147483647]
]

Output: [
  [3,-1,0,1],
  [2,2,1,-1],
  [1,-1,2,-1],
  [0,-1,3,4]
]

Example 2:

Input: [
  [0,-1],
  [2147483647,2147483647]
]

Output: [
  [0,-1],
  [1,2]
]

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] is one of {-1, 0, 2147483647}

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given grid.

Solution

Perform BFS by adding all chests to open. Prune if already assigned a value, as we are guaranteed to visit land in shortest path.

class Solution {
    inline static std::array<std::pair<int, int>, 4> OFFSETS = {{
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    }};
public:
    void islandsAndTreasure(vector<vector<int>>& grid) {
        const int WATER = -1;
        const int CHEST = 0;
        const int LAND = 2147483647;
        const int ROWS = grid.size();
        const int COLS = grid[0].size();
 
 
        std::queue<std::pair<int, int>> open;
 
        // CHESTS all start at level 0
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (grid[r][c] == CHEST) {
                    open.emplace(r, c);
                }
            }
        }
 
        // BFS
        while (!open.empty()) {
            auto [row, col] = open.front();
            open.pop();
            for (const auto [dr, dc] : OFFSETS) {
                auto r = row + dr; 
                auto c = col + dc;
                // Out of bounds
                if (r < 0 || c < 0 || r >= ROWS || c >= COLS) {
                    continue;
                }
                // Already assigned shortest path
                if (grid[r][c] != LAND) { continue; }
                grid[r][c] = grid[row][col] + 1;
                open.emplace(r, c);
            }
        }
    }
};
 

Starting at a chest cell, flood fill out counting depth. If we come across a LAND cell with lower cost, stop.

class Solution {
public:
    void islandsAndTreasure(vector<vector<int>>& grid) {
        const int WATER = -1;
        const int CHEST = 0;
        const int LAND = 2147483647;
        const int ROWS = grid.size();
        const int COLS = grid[0].size();
 
        std::function<void(int, int, int)> dfs;
        dfs = [&](int r, int c, int d) {
            // Out of bounds check
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS) {
                return;
            }
            // If non-land, skip (edge case of starting at chest)
            if (d > 0 && (grid[r][c] == CHEST || grid[r][c] == WATER) ) {
                return; 
            }
 
            // Land cell may be reachable by more than one chest
            // Ensure we track closest one
            // Better path already found, don't continue
            if (grid[r][c] < d) { return; }
 
            // Better path found, flood fill to neighbors
            grid[r][c] = d;
            dfs(r - 1, c, d + 1);
            dfs(r + 1, c, d + 1);
            dfs(r, c - 1, d + 1);
            dfs(r, c + 1, d + 1);
        };
 
        // Loop until we find a chest
        // Perform floodfill away from chest, counting
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (grid[r][c] == CHEST) {
                    dfs(r, c, 0);
                }
            }
        }
    }
};