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

Example 1:

Input: grid = [ [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: grid = [ [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.

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int,int>> que;
        for ( int i = 0; i < n; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                // 將所有陸地都放入隊列中
                if ( grid[i][j] == 1) que.push( {i,j} ); 
            }
        }

        vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        // 如果沒有陸地或者海洋，返回-1
        if ( que.size() == 0 || que.size() == n * n ) return -1;
        // 由於BFS的第一層遍歷是從陸地開始，因此遍歷完第一層之後distance應該是0
        int distance = -1;
        while (  !que.empty() ) {
            int que_size = que.size();
            distance++;
            while ( que_size-- ) {
                int x = que.front().first;
                int y = que.front().second;
                que.pop();
                // 對當前元素的各個方向進行搜索
                for ( auto dir : directions ) {
                    int i = x + dir[0];
                    int j = y + dir[1];
                    // 如果搜索到的新坐標超出範圍/陸地/已經遍歷過，則不搜索了
                    if ( i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 0 ) continue;
                    // 把grid中搜索過的元素設置為2
                    grid[i][j] = 2;
                    // 放入隊列中
                    que.push( {i,j} );
                }

            }

        }

        // 最終走了多少層才把海洋遍歷完
        return distance;
    }
};