# [LeetCode 827. Making A Large Island ](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/613/week-1-august-1st-august-7th/3835/)
### Daily challenge Aug 1, 2021 (HARD)

>You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.
>
>Return the size of the largest **island** in `grid` after applying this operation.
>
>An island is a 4-directionally connected group of 1s.

:::info
**Example 1:**
**Input:** grid = [[1,0],[0,1]]
**Output:** 3
**Explanation:** Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
:::

:::info
**Example 2:**
**Input:** grid = [[1,1],[1,0]]
**Output:** 4
**Explanation:** Change the 0 to 1 and make the island bigger, only one island with area = 4.
:::

:::info
**Example 3:**
**Input:** grid = [[1,1],[1,1]]
**utput** 4
**Explanation:** Can't change any 0 to 1, only one island with area = 4.
:::

:::warning
**Constraints:**
* n == grid.length
* n == grid[i].length
* 1 <= n <= 500
* grid[i][j] is either 0 or 1.
:::

---

### Approach 1 : DFS :bulb: + :book:
**`516 ms ( 71.61% )`** **`O(N^2)`**

* 步驟 :
>1. 先判斷 `grid[x][y] == 1` ---> 使用 **`DFS`** 計算每塊 `island` 的大小，同時將 `island` 給上 **`group_label`**。
>2. 再判斷 `grid[x][y] == 0` 周圍是否有相連的 `island`。

* DFS :
>* **`group_label`** 表示 `island` 組別。
>---> 從 `2` 開始編號 ( 因為 0、1 原本就存在 `grid` 裡面 )。
>**`group_area`** 表示每組 `island` 的 `area`。
>**`ans`** 代表當前最大的 `area`。
> 1. 往四個方向進行 **`DFS`**，尋找 `area`。
> 2. 將 `island` 的每個點賦予 `label` ---> **`grid[x][y] = gorup_label`**。
> 3. 最後將每組的 `area` 存入 `group_area` -> **`group_area[group_label] = dfs()`**。

* 判斷 `0` :
> * **`unordered_set<int> used`** 紀錄當前 `0` 走過的 `island`。
> ---> 可以避免當前的 `0` 有多個方向與同一個 `island` 相連。
> * 當 **`grid[x][y] == 0`** :
>> 1. 判斷四個方向是否有 `island` 相連。
>> ---> **`area += group_area[grid[next_x][next_y]]`**。
>> 2. 最後判斷新的 `area` 是否較大 ---> **`ans = max(ans, area)`**。

class Solution {
public:
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    map<int, int> group_area;
    
    
    int dfs(vector<vector<int>>& grid, int x, int y, int group_label){
        int area = 0;
        grid[x][y] = group_label; // label each area by group
        
        for(auto DIR : dir){
            int next_x = x + DIR[0];
            int next_y = y + DIR[1];
            
            if(next_x < 0 || next_x >= grid.size() ||
               next_y < 0 || next_y >= grid[0].size())  continue;
            
            if(grid[next_x][next_y] == 1)   area += dfs(grid, next_x, next_y, group_label);
        }
        
        return area + 1;
    }
    
    
    int largestIsland(vector<vector<int>>& grid) {
        int ans = 0;
        int group_label = 2;  // start from 2, beacuase 0、1 is matrix's original number
        
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[0].size(); j++){
                if(grid[i][j] == 1){
                    group_area[group_label] = dfs(grid, i, j, group_label);
                    ans = max(ans, group_area[group_label]);
                    group_label++;
                }
            }
        }
        
        
        for(int i=0; i<grid.size(); i++){
            for(int j=0; j<grid[0].size(); j++){
                if(grid[i][j] == 0){
                    unordered_set<int> used;
                    int area = 1;
                    for(auto DIR : dir){
                        int next_x = i + DIR[0];
                        int next_y = j + DIR[1];
                        
                        if(next_x < 0 || next_x >= grid.size() ||
                           next_y < 0 || next_y >= grid[0].size())   continue;
                        
                        group_label = grid[next_x][next_y];
                        
                        if(grid[next_x][next_y] > 1 && used.count(group_label) == 0){
                            area += group_area[grid[next_x][next_y]];
                            used.insert(group_label);
                        }
                    }
                    
                    ans = max(ans, area);
                }
            }
        }
        
        return ans;
    }
};