1162. 地圖分析

思路

寬度優先搜索，用 queue 紀錄需要擴散的點，往外擴散。
下圖展示了從左上角開始，把附近節點都擴散，標記為 1 的過程。

• 最初從 $(0, 0)$ 開始，往一旁的 $(0,1), (1,0)$ 擴散，加入 queue 當中
  • queue = {{0,1}, {1,0}}
• 取出queue隊首 $(0, 1)$ ，往四周擴散，把走訪到的 $(0,2),(1,1)$ 加入 queue。
  • queue = {{1,0}, {0,2}, {1,1}} 之後就是不斷地取出隊首，往周圍擴散，走訪到的新位置加入 queue，直到空為止。 為了避免無限迴圈，已經走訪過的位置要被標記，避免回頭，走到來時的路。

上面講述的情況，是指僅有一個源頭的情況，而源頭可以有很多個，下方展示了多源擴展的方式。
整個擴散過程都相同，只不過會有不同的來源，在走訪到時給不同的標記就行。

題目要在所有 0 當中，跟 1 最遠的距離，兩者分別代表海洋與陸地。
與其對每個 0 去做 bfs，不如反過來從所有的陸地區塊往海洋走訪。

• 第一次擴散到的海洋區域，只需要一步就能走到。
• 第二次擴散到的海洋區域，只需要兩步就能走到
• 第 $i$ 次擴散到的海洋區域，只需要 $i$ 步就能走到。

因此就按照介紹當中，多點擴散的想法，一步步往外擴散，並紀錄步數。

程式碼

1. 隊列

class Solution {
private:
    void printGrid(vector<vector<int>>& grid) { // 補助函數，幫忙知道每次擴張之後, grid 的樣子
        for(auto& vec : grid) {
            for(int& x : vec) {
                cout << x << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int, int>> q;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) { // 標記陸地的位置
                    q.push({i, j});
                }
            }
        }
        if(q.empty() || q.size() == n * n) return -1; // 全是陸地，或全是水
        int dir[5] = {-1, 0, 1, 0, -1};
        int step = 0;
        while(!q.empty()) {
            int size = q.size();
            // cout << "size = " << size << endl;
            while(size--) { // 將這一層往外擴散一次
                auto [x, y] = q.front(); q.pop();
                for(int i = 0; i < 4; i++) {
                    int nx = x + dir[i];
                    int ny = y + dir[i + 1];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 1) { // 1 代表已走訪
                        continue; 
                    }
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
            // printGrid(grid);
            step++;
        }
        // 最後被走訪的位置，就是答案，也就是廣度優先搜索時，往外擴張了幾次。
        return step - 1; // 最後一步之後，整個 grid 已經填滿，但會多出一步嘗試往外擴展，最後全失敗。
    }
};

2. 陣列模擬隊列

class Solution {
private:
    static const int MX = 1e4+1; // 100 * 100
    int q[MX][2];
    void printGrid(vector<vector<int>>& grid) { // 補助函數，幫忙知道每次擴張之後, grid 的樣子
        for(auto& vec : grid) {
            for(int& x : vec) {
                cout << x << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        int l = 0, r = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    q[r][0] = i;
                    q[r][1] = j;
                    r++;
                }
            }
        }
        if(r == 0 || r == n * n) return -1; // 全是陸地，或全是水
        int dir[5] = {-1, 0, 1, 0, -1};
        int step = 0;
        while(l < r) {
            int size = r - l;
            // cout << "size = " << r << " - " << l << " = " << size << endl;
            while(size--) { // 將這一層往外擴散一次
                int x = q[l][0];
                int y = q[l][1];
                l++;
                for(int i = 0; i < 4; i++) {
                    int nx = x + dir[i];
                    int ny = y + dir[i + 1];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 1) { // 1 代表已走訪
                        continue; 
                    }
                    grid[nx][ny] = 1;
                    q[r][0] = nx;
                    q[r][1] = ny;
                    r++;
                }
            }
            // printGrid(grid);
            step++;
        }
        return step - 1;
    }
};

3. 用地圖記錄步數

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int, int>> q;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) { // 標記陸地的位置
                    q.push({i, j});
                }
            }
        }
        if(q.empty() || q.size() == n * n) return -1; // 全是陸地，或全是水
        int dir[5] = {-1, 0, 1, 0, -1};
        int res;
        int step = 1;
        while(!q.empty()) {
            int size = q.size();
            while(size--) { // 將這一層往外擴散一次
                auto [x, y] = q.front(); q.pop();
                for(int i = 0; i < 4; i++) {
                    int nx = x + dir[i];
                    int ny = y + dir[i + 1];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] != 0) { // 不是 1 代表已經走訪
                        continue; 
                    }
                    grid[nx][ny] = step;
                    res = max(res, step);
                    q.push({nx, ny});
                }
            }
            step++;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n^2)$