题目描述

给定一个二维数组 A，每个格子为 0（表示海洋）或 1（表示陆地）。

一个合法的移动包括从一块陆地 4 方向到另一块陆地，或者从格子的边界走出。

返回以任何步数，我们都不能走出格子的陆地格子的数量。

样例

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

输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：
所有的 1 或者在边界上或者可以到达边界。

注意

• 1 <= A.length <= 500
• 1 <= A[i].length <= 500
• 0 <= A[i][j] <= 1
• 所有行都有相同的大小。

算法

(深度 / 宽度优先遍历) $O(nm)$

1. 从每个边界格子开始，使用 floodfill 算法扩展能到的格子。floodfill 可以用 DFS 或者 BFS 实现。
2. 最后统计出有多少个没有到的陆地格子。

时间复杂度

• 每个格子最多被遍历一次，故时间复杂度为 $O(nm)$。

空间复杂度

• 使用 DFS 要使用栈空间；使用 BFS 要队列空间，故空间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:

    void dfs(int x, int y, vector<vector<int>> &A) {
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int n = A.size(), m = A[0].size();
        if (x < 0 || x >= n || y < 0 || y >= m || A[x][y] == 0)
            return;
        A[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            dfs(tx, ty, A);
        }

    }

    int numEnclaves(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();

        for (int i = 0; i < n; i++) {
            dfs(i, 0, A);
            dfs(i, m - 1, A);
        }

        for (int j = 0; j < m; j++) {
            dfs(0, j, A);
            dfs(n - 1, j, A);
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (A[i][j] == 1)
                    ans++;

        return ans;
    }
};