827. 最大人工島

思路

給定一個 01 矩陣，有一次機會能修改其中一個位置的島嶼數值為 1，
可用可不用。找出可以得到的最大島嶼面積。

最樸素的想法，是讓每一個格子都修改一遍，
然後從這個被修改的格子往外擴散，找到當前這個格子所屬的島嶼大小。

• 如果島嶼原本就是 1：相當於沒有使用修改機會。
• 如果不是 1：有機會連接不同島嶼，讓面積變得更大，或是讓相鄰的島嶼面積 + 1。

因此，只要從被修改的格子擴散就好，
因為它所在的區域，才有可能讓面積更大。 以下是這個思路的程式碼：

洪水填充 TLE

class Solution {
private:
    static const int MX = 501;
    bool visited[MX][MX];
    int getArea(int i, int j, vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        for(int i = 0; i < n; i++) {
            fill(visited[i], visited[i] + m, false);
        }

        auto dfs = [&](this auto&&dfs, int i, int j) {
            if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == 0 || visited[i][j]) {
                return 0;
            }
            visited[i][j] = true;
            int sum = 0;
            sum += dfs(i + 1, j);
            sum += dfs(i - 1, j);
            sum += dfs(i, j + 1);
            sum += dfs(i, j - 1);
            return sum + 1;
        };

        return dfs(i, j);
    }
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) { // 將當前位置的地面修改為 1，然後從這個位置找到島嶼面積
                int temp = grid[i][j];
                grid[i][j] = 1;
                res = max(res, getArea(i, j, grid));
                grid[i][j] = temp;
            }
        }
        return res;
    }
};

這樣做會導致超時，因為即使已經計算過島嶼的面積，每次都還是會重新遍歷一遍。
為了避免重複計算，在使用修改機會之前，用洪水填充算法，給各自島嶼一個編號，並將編號對應的島嶼面積，存在哈希表中。
接下來，遍歷所有節點，假如這個位置是海水，那麼就試著使用填充機會，
把四方的島嶼累計之後，加上這個被修改為陸地的格子，列入參考答案。

程式碼

洪水填充

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();

        auto dfs = [&](this auto&&dfs, int i, int j, int id) {
            if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != 1) {
                return 0;
            }
            // grid[i][j] = 1
            grid[i][j] = id;
            int sum = 0;
            sum += dfs(i + 1, j, id);
            sum += dfs(i - 1, j, id);
            sum += dfs(i, j + 1, id);
            sum += dfs(i, j - 1, id);
            return sum + 1;
        };

        unordered_map<int, int> umap; // 紀錄每個 id 對應的面積
        int res = 0;
        int id = 2; // id 從 2 開始，跟 01 矩陣的元素不重複
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) { 
                if(grid[i][j] == 1) {
                    int area = dfs(i, j, id);
                    umap[id++] = area;
                    res = max(res, area);
                }
            }
        }
        vector<bool> used(id + 1); // 記錄四個方向都有哪些編號的島嶼被連接
        int dir[5] = {-1, 0, 1, 0, -1}; // 四方向
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 0) { // 這個位置使用修改操作不會浪費
                    fill(used.begin(), used.end(), false);
                    int curArea = 1; // 自己位置的大小
                    for(int k = 0; k < 4; k++) {
                        int ni = i + dir[k];
                        int nj = j + dir[k + 1];
                        if(ni < 0 || ni >= n || nj < 0 || nj >= m) {
                            continue;
                        }
                        int neighborID = grid[ni][nj];
                        if(!used[neighborID]) {
                            curArea += umap[neighborID];
                            used[neighborID] = true;
                        }
                    }
                    res = max(res, curArea);
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(mn)$
• 空間複雜度：$O(mn)$