1162. As Far from Land as Possible

1162. As Far from Land as Possible (Medium)

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

Companies:
Uipath

Related Topics:
Breadth-first Search, Graph

Similar Questions:

• Shortest Distance from All Buildings (Hard)

Solution 1. Brute Force

For each water cell, compute its minimal distance to all lands. The maximum of those minimal distances is the answer.

Note that if dist is already smaller than or equal to the current best answer ans, this cell should be skipped because it can't yield better result (if (dist <= ans) break;).

// OJ: https://leetcode.com/problems/as-far-from-land-as-possible/
// Author: github.com/lzl124631x
// Time: O(MNL) where grid is of size M*N and L is the count of lands.
// Space: O(L)
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        vector<pair<int, int>> lands;
        int M = grid.size(), N = grid[0].size(), ans = -1;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 1) lands.emplace_back(i, j);
            }
        }
        if (lands.empty() || M * N == lands.size()) return -1;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 1) continue;
                int dist = INT_MAX;
                for (auto &p : lands) {
                    int d = abs(p.first - i) + abs(p.second - j);
                    dist = min(dist, d);
                    if (dist <= ans) break;
                }
                ans = max(ans, dist);
            }
        }
        return ans;
    }
};

Solution 2. BFS

Starts from lands, do BFS layer by layer. The maximum layer number you get is the answer.

// OJ: https://leetcode.com/problems/as-far-from-land-as-possible/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        int M = grid.size(), N = grid[0].size(), ans = -1;
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 1) q.emplace(i, j);
            }
        }
        if (q.empty() || M * N == q.size()) return -1;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto p = q.front();
                q.pop();
                for (auto &dir : dirs) {
                    int x = p.first + dir[0], y = p.second + dir[1];
                    if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y]) continue;
                    q.emplace(x, y);
                    grid[x][y] = 1;
                }
            }
            ++ans;
        }
        return ans;
    }
};