542-01矩阵

LeetCode 542. 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

method: 多源BFS

因为是BFS，每个点第一次被更新的时候，就是它最接近起点的时候，所以更新完就是最小值，只更新一次就可以了

所以需要用used数组来标记这个点有没有更新过，也可以把1的位置改为无穷大或-1之类的，只要被更新过就不会是原来的无穷大或-1了，这样也能起到标记的作用

int next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    queue<pair<int, int>> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 0) q.push({i, j}); // 为0的点入队
            else mat[i][j] = INT_MAX;
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + next[k][0];
            int ny = y + next[k][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && mat[nx][ny] == INT_MAX) {
                mat[nx][ny] = mat[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return mat;
}

---

LeetCode 1162. 地图分析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」(Manhattan Distance)：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

method: 多源BFS

int next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int maxDistance(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) q.push({i, j});
            else grid[i][j] = -1;   // 用来标记是否更新过
        }
    }
    if (q.size() == 0 || q.size() == m * n) return -1;  // 全0或全1
    int res = 0;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        res = grid[x][y];   // 记录最后一个出队节点的值
        for (int k = 0; k < 4; k++) {
            int nx = x + next[k][0];
            int ny = y + next[k][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == -1) {
                grid[nx][ny] = grid[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return res - 1;
}