图论第2天----第1020题、第130题

# 图论第2天----第1020题、第130题

文章目录

一、第1020题--飞地的数量
二、第130题--被围绕的区域

又继续开始修行，把图论这块补上，估计要个5-6天时间。

一、第1020题–飞地的数量

跟前面做的思路差不多，其实有另外一种思路。我这里是在遍历每块岛屿时，判断是否四周都是水，进而再统计数量。另一种思路，与130思路差不多，从边上开始遍历，要遍历2遍。

class Solution {
public:
    int count;
    int result = 0;
    bool flag;
    int dir[4][2] = {0,1,1,0,0,-1,-1,0};

    void dfs(vector>& grid, vector>& visited, int x, int y){
        for (int i=0; i<4; i++){
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if(nextx <0 || nextx >=grid.size() || nexty <0 || nexty >= grid[0].size()){
                flag = true;
                continue;
            }
            if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
                visited[nextx][nexty] = true;
                count++;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

    int numEnclaves(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector> visited(n, vector(m, false));
        for(int i=0; i

二、第130题–被围绕的区域

遍历2遍。第一遍从边上开始遍历，把边上的岛屿做标记，记为’A’。这样边上的岛屿（‘A’）与中间的岛屿(‘O’)区分开了。第二遍遍历时，每个元素都遍历到，把’O’变为’X’，把’A’变为’O’，就把边上边上的岛屿留下了。

class Solution {
public:
    int dir[4][2] = {0,1,1,0,0,-1,-1,0};
    void dfs(vector>& 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] == 'X' || board[nextx][nexty] == 'A') continue;
            dfs(board, nextx, nexty);
        }
    }

    void solve(vector>& board) {
        int n = board.size();
        int m = board[0].size();
        for(int i=0; i