leetcode 1020. 飞地的数量

2022-02-12

题目

给一个大小为m*n的二进制矩阵grid，0表示海洋，1表示陆地

一次移动指：从一个陆地单元格上走到另一个相邻陆地单元格或者跨越grid的边界

返回网格中无法在任意次数移动中离开网格边界的陆地单元格的数量

思路

读题可以知道，要求的就是被0包围起来的1的数量。因此可以对四个边界上的1做BFS/DFS，将不满足要求（即可以跨越边界）的1变为0。再统计剩下的1的数量。

以下给出DFS的实现

代码

class Solution {
    // 深度优先遍历，将一整块1变为0
    int dx[4]{0, 0, -1, 1}, dy[4]{1, -1, 0, 0};
    void dfs(vector<vector<int>>& grid, int x, int y){
        int n=grid.size(), m=grid[0].size();
        grid[x][y]=0;
        for(int i=0;i<4;++i){
            int newx=x+dx[i], newy=y+dy[i];
            if(newx>=0 && newx<n && newy>=0 && newy<m && grid[newx][newy]==1){
                dfs(grid, newx, newy);
            }
        }
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        // 处理边界的1
        for(int j=0;j<m;++j){
            if(grid[0][j]==1)   dfs(grid, 0, j);
            if(grid[n-1][j]==1) dfs(grid, n-1, j);
        }
        for(int i=1;i<n-1;++i){
            if(grid[i][0]==1)   dfs(grid, i, 0);
            if(grid[i][m-1]==1) dfs(grid, i, m-1);
        }
        // 统计答案
        int ans=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(grid[i][j]==1)   ++ans;
            }
        }
        return ans;
    }
};