Leetcode 827. Making A Large Island

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: 3
Explanation: 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: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: 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<int> &parent,int target){
 4         while(parent[target] != target){
 5             target = parent[target];
 6         }
 7         return target;
 8     }
 9     void Union(vector<int> &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<vector<int>>& grid) {
19         int m = grid.size();
20         int n = grid[0].size();
21         vector<int> parent(m*n,0);
22         vector<vector<int>> 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<int,int> 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<int> 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 };