Problem:

 

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

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

Example 2:

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

Example 3:

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

 

Notes:

• 1 <= grid.length = grid[0].length <= 50.
• 0 <= grid[i][j] <= 1.

 

Solution:

　　Hard题中的easy题，首先用一个哈希表chunk用每个联通块根节点映射该联通块对应的大小，用Union Find即可，然后对于grid中每个值为0的位置，若其上下左右某个位置为1，则找到该位置对应的根节点，在chunk中找到其对于的联通块的大小，加到square中即可，注意有可能上下左右四个方位中的某些1是联通的，所以我在循环内部用了一个哈希集root记录了访问过的根节点避免重复相加联通块。注意边界即可。

Code:

 

1 class Solution { 2 public: 3     int Find(vector
     
       &parent,int target){ 4         while(parent[target] != target){ 5             target = parent[target]; 6         } 7         return target; 8     } 9     void Union(vector
      
        &parent,int x,int y){10         int px = Find(parent,x);11         int py = Find(parent,y);12         if(px == py) return;13         if(px < py) 14             parent[py] = px;15         else 16             parent[px] = py;17     }18     int largestIsland(vector
       
        
         >& grid) {19         int m = grid.size();20         int n = grid[0].size();21         vector
         
           parent(m*n,0);22         vector
          
           
            > dir({ { 0,1},{ 0,-1},{ 1,0},{-1,0}});23 for(int i = 0;i != m*n;++i){24 parent[i] = i;25 }26 for(int i = 0;i != m;++i){27 for(int j = 0;j != n;++j){28 if(grid[i][j] == 0) continue;29 for(int k = 0;k != dir.size();++k){30 if(i+dir[k][0] < 0 || i+dir[k][0] >= m || j+dir[k][1] < 0 || j+dir[k][1] >= n)31 continue;32 if(grid[i+dir[k][0]][j+dir[k][1]] == 1)33 Union(parent,i*n+j,(i+dir[k][0])*n+j+dir[k][1]);34 }35 }36 }37 int maximal = 0;38 unordered_map
            
              chunk;39 for(int i = 0;i != m;++i){40 for(int j = 0;j != n;++j){41 if(grid[i][j] == 0) continue;42 int root = Find(parent,i*n+j);43 chunk[root]++;44 maximal = max(maximal,chunk[root]);45 }46 }47 for(int i = 0;i != m;++i){48 for(int j = 0;j != n;++j){49 if(grid[i][j] == 1) continue;50 int square = 1;51 unordered_set
             
               root;52 for(int k = 0;k != dir.size();++k){53 if(i+dir[k][0] < 0 || i+dir[k][0] >= m || j+dir[k][1] < 0 || j+dir[k][1] >= n)54 continue;55 if(grid[i+dir[k][0]][j+dir[k][1]] == 1){56 int r = Find(parent,(i+dir[k][0])*n+j+dir[k][1]);57 if(root.find(r) == root.end()){58 root.insert(r);59 square += chunk[r];60 }61 }62 }63 maximal = max(maximal,square);64 }65 }66 return maximal;67 }68 };