【寬度優先搜尋】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;
    }
};