1162. As Far from Land as Possible

O(mn) time O(1) space
↘扫描一遍再↖扫描一遍，第一次扫可以得到到左上方land的最近距离，第二次扫可以得到到剩余land的最近距离，取最小值来更新全局最大值

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int N = grid.size();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] != 1) { // 注意是不为1，只有1是land
                    grid[i][j] = 200; // 所有water初始化为inf，这里用200防止后面overflow
                    if (i > 0) {
                        grid[i][j] = min(grid[i][j], grid[i - 1][j] + 1); // 向下propagate，要不是根据inf要不就是根据land
                    }
                    if (j > 0) {
                        grid[i][j] = min(grid[i][j], grid[i][j - 1] + 1); // 向右propagate
                    }
                }
            }
        }
        int res = 0;
        for (int i = N - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                if (grid[i][j] != 1) {
                    if (i + 1 < N) {
                        grid[i][j] = min(grid[i][j], grid[i + 1][j] + 1); // 向上propagate
                    }
                    if (j + 1 < N) {
                        grid[i][j] = min(grid[i][j], grid[i][j + 1] + 1); // 向左propagate
                    }
                    res = max(res, grid[i][j]);
                }
            }
        }
        return res % 200 - 1; // 最后结果要不是inf即200要不就是距离，最后要减1是因为从land开始propagate，land的值是1
    }
};

bfs O(mn) time O(min(m, n)) space

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        N = grid.size();
        queue<pair<int, int>> q;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) { // 横向扫每行找到边缘的land
                if (j > 0 && grid[i][j - 1] == 0 && grid[i][j] == 1) {
                    q.emplace(i, j);
                }
                if (j + 1 < N && grid[i][j] == 1 && grid[i][j + 1] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        for (int j = 0; j < N; ++j) {
            for (int i = 0; i < N; ++i) { // 纵向扫每列找到边缘的land
                if (i > 0 && grid[i - 1][j] == 0 && grid[i][j] == 1) {
                    q.emplace(i, j);
                }
                if (i + 1 < N && grid[i][j] == 1 && grid[i + 1][j] == 0) {
                    q.emplace(i, j);
                }
            }
        }
        int res = -1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) { // bfs逐层扫描
                auto [r, c] = q.front(); q.pop();
                for (int j = 0; j < 4; ++j) {
                    int rr = r + dr[j], cc = c + dc[j];
                    if (isInBound(rr, cc) && grid[rr][cc] == 0) {
                        grid[rr][cc] = 2;
                        q.emplace(rr, cc);
                    }
                }
            }
            ++res;
        }
        return res;
    }

    bool isInBound(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }

    int N, dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
};