代码随想录（番外）图论3|1020. 飞地的数量|130. 被围绕的区域

代码随想录（番外）图论3|1020. 飞地的数量|130. 被围绕的区域

1020. 飞地的数量

class Solution {
public:
    int dir[4][2]={0,1,1,0,0,-1,-1,0};
    int count;
    void dfs(vector<vector<int>>& grid,int x,int y)
    {
        grid[x][y]=0;
        count++;
        for(int i=0;i<4;i++)
        {
            int nextx=x+dir[i][0];
            int nexty=y+dir[i][1];

            if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size()) continue;
            if(grid[nextx][nexty]==0) continue;

            dfs(grid,nextx,nexty);
        }
        return;
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        
        for(int i=0;i<n;i++)
        {
            if(grid[0][i]==1) dfs(grid,0,i);
            if(grid[m-1][i]==1) dfs(grid,m-1,i);

        }

        for(int j=0;j<m;j++)
        {
            if(grid[j][0]==1) dfs(grid,j,0);
            if(grid[j][n-1]==1) dfs(grid,j,n-1);
        }

        count=0;

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1) dfs(grid,i,j);
            }
        
        return count;
    }
};
/*
本题是通过把四周的边界区域归0，然后最后遍历全部
之后可以得出图中飞地，但是要特别注意区域边界值问题，最后画图
确定边界范围，这样不容易出错。
*/
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

1021. 130. 被围绕的区域

class Solution {
public:
    int dir[4][2]={0,1,1,0,0,-1,-1,0};
    void dfs(vector<vector<char>>& board,int x,int y)
    {
        board[x][y]='A';
        for(int i=0;i<4;i++)
        {
            int nextx=x+dir[i][0];
            int nexty=y+dir[i][1];
            if(nextx<0||nexty<0||nextx>=board.size()||nexty>=board[0].size()) continue;
            if(board[nextx][nexty]=='A'||board[nextx][nexty]=='X') continue;

            dfs(board,nextx,nexty);
  
        }
    }
    void solve(vector<vector<char>>& board) {
        int m=board.size(),n=board[0].size();

        for(int i=0;i<m;i++)
        {
            if(board[i][0]=='O') dfs(board,i,0);
            if(board[i][n-1]=='O') dfs(board,i,n-1);

        }

        for(int j=0;j<n;j++)
        {
            if(board[0][j]=='O') dfs(board,0,j);
            if(board[m-1][j]=='O') dfs(board,m-1,j);            
        }

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                if(board[i][j]=='O') board[i][j]='X';
                if(board[i][j]=='A') board[i][j]='O';

            }
    }
};

/*
其中算法还是比较巧妙的不用再定义一个二维数组来标记
一直出小错误，
1.边界，一定一定一定要在纸上画。
2.注意边界dfs遍历
恼火。
*/
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