【宽度优先搜索】Leetcode 1162. 地图分析

Leetcode 1162. 地图分析

题目描述：你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

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

如果网格上只有陆地或者海洋，请返回 -1。

这道题属于矩阵中的宽度优先搜索，代码如下：

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<pair<int, int>> DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        queue<pair<int, int>> Queue;
        bool hasOcean = false;//标记是否有海洋

        //1. 先把所有的陆地都入队
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (1 == grid[i][j]) {
                    Queue.push(make_pair(i, j));
                }
            }
        }
        
        //2. 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋
        pair<int, int> lastPoint;//记录最后被遍历到的点
        while (!Queue.empty()) {
            auto [x, y] = Queue.front();//取一个坐标
            lastPoint = make_pair(x, y);
            Queue.pop();
            //遍历4个方向
            for (auto [dx, dy] : DIRECTIONS) {
                int new_x = x + dx;
                int new_y = y + dy;
                if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || 0 != grid[new_x][new_y]) {
                    continue;
                }
                grid[new_x][new_y] = grid[x][y] + 1;//这里直接改变了原数组
                hasOcean = true;//找到了海洋
                Queue.push(make_pair(new_x, new_y));//改变之后插入队列
          }
        }

        if (!hasOcean) {
            return -1;
        }
        return grid[lastPoint.first][lastPoint.second] - 1;
    }
};