原文链接: https://leetcode-cn.com/problems/number-of-enclaves

英文原文

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

 

Example 1:

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Example 2:

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] is either 0 or 1.

中文题目

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

通过代码

高赞题解

[]
class Solution {
    int row, col;
    int[][] A;
    public int numEnclaves(int[][] A) {
        if(A == null || A.length == 0) return 0;
        this.A = A;
        this.row = A.length;
        this.col = A[0].length;

        // 淹没所有和边界相接的陆地
        for (int i = 0; i < row; i++) {
            dfs(i, 0);
            dfs(i, col - 1);
        }
        for (int i = 0; i < col; i++) {
            dfs(0, i);
            dfs(row - 1, i);
        }
        // 统计剩下的飞陆
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(A[i][j] == 1) count++;
            }
        }
        return count;
    }

    /**
     * 把此大陆淹没，即把 1 变成 0
     * @param r,c DFS 起点
     */
    public void dfs(int r, int c){
        if(A[r][c] == 0) return;

        A[r][c] = 0;
        if(r > 0       ) { dfs(r - 1, c);       }
        if(c > 0       ) { dfs(r,     c - 1);   }
        if(r < row - 1 ) { dfs(r + 1, c);       }
        if(c < col - 1 ) { dfs(r,     c + 1);   }
    }
}

统计信息

通过次数	提交次数	AC比率
10462	19095	54.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言