827. Making A Large Island

 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.

 

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.

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.

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

 

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] is either 0 or 1.

class Solution {

public:

    int largestIsland(vector<vector<int>>& grid) {

        int rows = grid.size();

        if (rows == 0) {

            return 0;

        }

        int cols = grid[0].size();

        

        int index = 2; // So that this won't conlict with the original, 0 or 1.

        unordered_map<int, int> mp;

        for (int i = 0; i < rows; i++) {

            for (int j = 0; j < cols; j++) {

                if (grid[i][j] == 1) {

                    int count = 0;

                    dfs(grid, i, j, count, index);

                    mp[index] = count;

                    index++;

                }

            }

        }

        

        int ans = 0;

        bool any_zero = false;

        for (int i = 0; i < rows; i++) {

            for (int j = 0; j < cols; j++) {

                if (grid[i][j] == 0) {

                    any_zero = true;

                    ans = max(ans, check(grid, i, j, mp));

                }

            }

        }

        if (!any_zero) {

            return rows*cols;

        }

        return ans;

    }

    

    void dfs(vector<vector<int>>& grid, int i, int j, int& count, int index) {

        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1) {

            return;

        }

        count++;

        grid[i][j] = index;

        dfs(grid, i + 1, j, count, index);

        dfs(grid, i - 1, j, count, index);

        dfs(grid, i , j + 1, count, index);

        dfs(grid, i, j - 1, count, index);

    }

    

    int check(vector<vector<int>>& grid, int i, int j, unordered_map<int, int>& mp) {

        int ans = 1;

        unordered_set<int> st;

        if (valid(grid, i - 1, j) && st.count(grid[i - 1][j]) == 0) {

            ans += mp[grid[i - 1][j]];

            st.insert(grid[i - 1][j]);

        }

        if (valid(grid, i + 1, j) && st.count(grid[i + 1][j]) == 0) {

            ans += mp[grid[i + 1][j]];

            st.insert(grid[i + 1][j]);

        }

        if (valid(grid, i, j - 1) && st.count(grid[i][j - 1]) == 0) {

            ans += mp[grid[i][j - 1]];

            st.insert(grid[i][j - 1]);

        }

        if (valid(grid, i, j + 1) && st.count(grid[i][j + 1]) == 0) {

            ans += mp[grid[i][j + 1]];

            st.insert(grid[i][j + 1]);

        }

        return ans;

    }

    

    bool valid(vector<vector<int>>& grid, int i, int j) {

        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {

            return false;

        }

        return true;

    }

    

};