LeetCode-1020 飞地的数量（dfs）

骑猪看日落 2022-02-21 13:07 98阅读 0赞

给出一个二维数组 `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.  所有行的大小都相同

首先吐槽一下中国版LeetCode的C提交，**提交总是显示执行出错**，后来我上了英文原版网站找到了这道题，发现函数的最后一个参数的数据类型与中国版的不同，**英文原版传入的是指针**。

**思路：**

首先**遍历整个矩形的四条边，找到值为1的点，将这些点对应的dp数组的值置为true，并从这些点出发进行dfs，将所有能搜索到的值为1的点对应的dp数组的值都置为true（表示该点可以走出边界）。最后遍历整个矩形，找到值为1且对应的dp数组的值为false的点就让sum加1**，最后返回sum。

上AC代码（英文原版的C提交）：

int numEnclaves(int** A, int ARowSize, int *AColSizes) {
        bool dp[501][501];
        
        void dfs(int x,int y)
        {
            if(dp[x][y])
                return;
            dp[x][y]=true;
            int dx,dy;
            for(dx=-1;dx<=1;dx++)
            {
                for(dy=-1;dy<=1;dy++)
                {
                    if((dx==0||dy==0)&&x+dx>=0&&x+dx<ARowSize&&y+dy>=0&&y+dy<*AColSizes&&A[x+dx][y+dy]==1)
                    {
                        dfs(x+dx,y+dy);
                    }
                }
            }
        }
        int i,j;
        memset(dp,0,sizeof(dp));
        for(i=0;i<*AColSizes;i++)
        {
            if(A[0][i]==1)
            {
                dfs(0,i);
            }
            if(A[ARowSize-1][i]==1)
            {
                dfs(ARowSize-1,i);
            }
        }
        for(i=0;i<ARowSize;i++)
        {
            if(A[i][0]==1)
            {
                dfs(i,0);
            }
            if(A[i][*AColSizes-1]==1)
            {
                dfs(i,*AColSizes-1);
            }
        }
        
        int sum=0;
        for(i=0;i<ARowSize;i++)
        {
            for(j=0;j<*AColSizes;j++)
            {
                if(A[i][j]==1)
                {
                    if(dp[i][j]==false)
                        sum++;
                }
            }
        }
        return sum;
    }