Breadth-first Search - Middle Level - Question 1

Breadth-first Search - Middle Level - Question 1

Leetcode 1162  As Far from Land as Possible

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. If no land or water exists in the grid, return -1.

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|.

Constraints:

n == grid.length

n == grid[i].length

1 <= n <= 100

grid[i][j] is 0 or 1

Analysis:

One way to solve this problem is that: for each water position, we run a bfs search to the find the shortest distance to the land. Then the get the maximum of these shortest distances. The time complexity is O(n^4), which is too large to this question.

Alternatively, we can start with all lands, then do a bsf search. The last find water should have the largest distance to the land. The time complexity is O(n^2). 

See the code below:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> visit (n, vector<int>(n, 0));
        queue<pair<int,int>> q;
        vector<int> dirs={-1, 0, 1, 0, -1};
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j]==1) {
                    q.push({i,j});
                    visit[i][j]=1;
                }
            }
        }
        if(q.empty() || (int)q.size() == n*n) return -1;
        int res = 0;
        while (q.size()) {
            ++res;
            int t = q.size();
            // cout<<t<<endl;
            for(int i=0; i<t; ++i) {
                auto a = q.front();
                q.pop();
                for(int k=0; k+1<dirs.size(); ++k) {
                    int x= a.first + dirs[k], y=a.second + dirs[k+1];
                    if(x<0 || x>=n || y<0 || y>=n || grid[x][y] || visit[x][y]) continue;
                    q.push({x,y});
                    visit[x][y]=1;
                }
            }
        }
        return res - 1;
    }
};

Upper Layer