leetcode 827. Making A Large Island

Posted on | In , |

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
class Solution {
public:
    int m,n;
     map<int,int> mapp;
    int largestIsland(vector<vector<int>>& grid) {
        int color=1;
        m=grid.size();
        n=grid[0].size();
        
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]==1)
                {
                    color++;
                    mapp[color]=getArea(i,j,grid,color);
                    
                }    
            }      
        }
       int areas=0,ans=0;
        for(int x=0;x<m;x++){
            for(int y=0;y<n;y++){
                if(grid[x][y]==0){
                      set<int> s;
                    areas=1;
                    for(int i=0;i<4;i++)
                    {
                 
                       
                        int newx=x+dir[i][0];
                        int newy=y+dir[i][1];
                         if(newx<0||newx>=m||newy<0||newy>=n) continue;
                        int color=grid[newx][newy];
                      s.insert(color);//用集合 可能（x,y）上面和左边是同一个连通分量 同一个连通分量的面积只加一次
                    } 
                    for(auto c:s){
                        areas+=mapp[c];
                      //!!  cout<<x<<" "<<y<<"  "<<c<<" "<<mapp[c]<<endl; 填充(x,y)这点后所能形成的连通分量的面积‘’
                    }
                    
                    
                    ans=max(ans,areas);
                    }                    
                    
                    
                    
                }
            }
            
          if(areas==0) return m*n;  
        return ans;
        }
        
        
        

    int getArea(int x,int y,vector<vector<int>> &grid,int color){
    
        if(x<0||x>=m||y<0||y>=n) return 0;
     
        if(grid[x][y]!=1) return 0;//被標記過
        
        grid[x][y]=color;
    
        return 1+getArea(x-1,y,grid,color)+getArea(x+1,y,grid,color)+getArea(x,y+1,grid,color)+getArea(x,y-1,grid,color);  
    }
};