1117. As Far from Land as Possible

• Difficulty: Medium

• Topics: Breadth-first Search, Graph

• Similar Questions:

  • Shortest Distance from All Buildings

Problem:

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] is 0 or 1

Solutions:

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        if (n == 0) return 0;

        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    q.push({i, j});
                }
            }
        }

        int distance = -1;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto coord = q.front(); q.pop();
                for (int d = 0; d < 4; ++d) {
                    int row = coord.first + directions[d][0];
                    int col = coord.second + directions[d][1];
                    if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 0) {
                        q.push({row, col});
                        grid[row][col] = 1;
                    }
                }          
            }
            ++distance;
        }

        return distance <= 0 ? -1 : distance;
    }

private:
    int directions[4][2] = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

};