1020. Number of Enclaves-飞地的数量

给你一个大小为m x n的二进制矩阵grid，其中0表示一个海洋单元格、1表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过grid的边界。

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

示例 1：

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

示例 2：

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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j]的值为0或1

1.DFS
Python:

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if grid[i][j] == 0 or grid[i][j] == 2:
                return 
            else:
                grid[i][j] = 2
                lis = [(-1, 0), (1, 0), (0, -1), (0, 1)]
                for item in lis:
                    x = i + item[0]
                    y = j + item[1]
                    if 0 <= x < row and 0 <= y < col:
                        dfs(x, y)
        row = len(grid)
        col = len(grid[0])
        for i in range(row):
            if grid[i][0] == 1:
                dfs(i, 0)
            if grid[i][col-1] == 1:
                dfs(i, col-1)
        for j in range(col):
            if grid[0][j] == 1:
                dfs(0, j)
            if grid[row-1][j] == 1:
                dfs(row-1, j)
        total = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    total += 1
        return total

Java:

class Solution {
    public int numEnclaves(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        for(int i = 0; i < row; i++)
        {
            if(grid[i][0] == 1)
                dfs(grid, i, 0);
            if(grid[i][col-1] == 1)
                dfs(grid, i, col-1);
        }
        for(int j = 0; j < col; j++)
        {
            if(grid[0][j] == 1)
                dfs(grid, 0, j);
            if(grid[row-1][j] == 1)
                dfs(grid, row-1, j);           
        }

        int total = 0;
        for(int i = 0; i < grid.length; i++)
        {
            for(int j = 0; j < grid[0].length; j++)
            {
                if(grid[i][j] == 1)
                    total++;
            }
        }
        return total;
    }

    public void dfs(int[][] grid, int i, int j)
    {
        if(grid[i][j] == 0 || grid[i][j] == 2)
        {
            return;
        }
        grid[i][j] = 2;
        int[][] pos = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int[] p: pos)
        {
            int x = i + p[0];
            int y = j + p[1];
            if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)
            {
                dfs(grid, x, y);
            }
        }
    }
}