飞地的数量

题目链接

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

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

示例:

输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释： 
有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

思路

解法一：

使用深度优先遍历法， 可将问题看成一个联通分量中是否有在边界上的点。

  1. 对所有接触边界的联通分量进行标记；
  2. 设置一个 flag，用于标记是否在边界上；
  3. 统计单元格为1且不再边界上的邻近点进行累加。
class Solution {

private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int m, n;
    int dfs(vector<vector<int>>& grid, int x, int y, bool &flag) {  //这里是bool &flag
        if (x < 0 || x>= m || y < 0 || y >= n || grid[x][y] != 1) { // 坐标不符合或单元格的值为0
            return 0;
        }
        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) { // 若在边界上
            flag = true;
        }
        int res = 1;
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++)
        {
            res += dfs(grid, x + dirs[i][0], y + dirs[i][1], flag);
        }
        return res;
    }
    
public:
    
    int numEnclaves(vector<vector<int>>& grid) {
        int ans = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) 
            {
                if (grid[i][j] == 1) {
                    bool flag = false; //用flag判断是否在边界上
                    int result = dfs(grid, i, j, flag);
                    if (!flag) {
                        ans += result;
                    }
                }
            }
        }
        return ans;
    }
};