# 1162. As Far from Land as Possible
###### tags: `leetcode` `daily` `BFS`

[題目連結](https://leetcode.com/problems/as-far-from-land-as-possible/)

# Method BFS
:::info
:bulb: **作法講解**:
we want to find distance to the nearest land cell is maximized.
it's hard to find the distance start from water,
but we can find the distance easily start from land.

step 1, scan all the cell in grid, if the cell is land, add the cell into queue.
and mark the cell is visited.

stel 2, for each round, initially step = 1,
we can scan for each cell in queue, check top, left, right, down position we called next position,
if the next position, it's not visited, add the next position into queue,
and mark the next position is visited, set output = step.
step 3, add step by 1, goto do step 2 until queue is empty.
:::

TC: O(N^2) SC: O(N^2)
:::spoiler 完整程式碼

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        queue<pair<int, int>> q;
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int step = 0;
        int output = 0;
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(grid[i][j]) {
                    q.push({i, j});
                    visited[i][j] = true;
                }
            }
        }
        while(!q.empty()) {
            int size = q.size();
            step++;
            for(int i = 0 ; i < size ; i++) {
                int y = q.front().first;
                int x = q.front().second;
                q.pop();

                for(int k = 0 ; k < 4 ; k++) {
                    int ny = y + dirs[k][0];
                    int nx = x + dirs[k][1];
                    if((ny >= 0) && (ny < n) && (nx >= 0) && (nx < n) && (visited[ny][nx] == false)) {
                        visited[ny][nx] = true;
                        q.push({ny, nx});
                        output = step;
                    }
                }
            }
        }
        return (output == 0) ? -1 : output;
    }
};

:::