640，BFS和DFS两种方式解飞地的数量

Original 博哥数据结构和算法 2022-05-01

问题描述

来源：LeetCode第1020题

难度：中等

给你一个大小为mxn的二进制矩阵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

DFS（深度优先搜索）解决

这道题叙述的比较绕，矩阵中的值要么是0要么是1，其中1表示的是陆地，他的意思是矩阵中有多少陆地不能到达边界。在很久以前讲过445，BFS和DFS两种方式解岛屿数量，和这题很类似。所以这题也有两种解决方式，一种就是DFS，第一遍先沿着矩阵的4条边进行搜索，如果是1就把他变成0，并且和他挨着的（上下左右）为1的也变成0，一直这样循环下去……，第二遍在遍历矩阵统计1的个数，来看下代码

public int numEnclaves(int[][] grid) {
    //第一次遍历，沿着矩阵的4条边查找，如果遇到1就把他变成0
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            //只能从矩阵的上下左右4条边遍历
            if (i == 0 || j == 0 || i == m - 1
                    || j == n - 1)
                if (grid[i][j] == 1)
                    dfs(grid, m, n, i, j);
        }
    }

    //第二次遍历，统计矩阵中1的个数
    int res = 0;
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            //如果是1就加1
            if (grid[i][j] == 1)
                res++;
        }
    }
    return res;
}

//往当前位置的上下左右4个方向查找
private void dfs(int grid[][], int m, int n, int i, int j) {
    //查找的时候不能越界，也就是不能跑到矩阵的外面，并且当前位置必须是1
    if (i >= 0 && i <= m - 1 && j >= 0 &&
            j <= n - 1 && grid[i][j] == 1) {
        //把当前位置变为0
        grid[i][j] = 0;
        dfs(grid, m, n, i - 1, j);//往上搜索
        dfs(grid, m, n, i + 1, j);//往下搜索
        dfs(grid, m, n, i, j - 1);//往左搜索
        dfs(grid, m, n, i, j + 1);//往右搜索
    }
}

BFS（广度优先搜索）解决

无论是DFS还是BFS，实现原理都差不多。BFS是先遍历矩阵的4条边，找到值为1的位置，把他们统一放到一个队列中，顺便把他们的值改为0，然后在遍历这个队列，队列中每个元素在矩阵中的上下左右4个方向都要遍历，如果是1就继续加入到队列中……

public int numEnclaves(int[][] grid) {
    Queue<int[]> queue = new LinkedList<>();
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            //只能从矩阵的上下左右4条边遍历
            if (i == 0 || j == 0 || i == m - 1
                    || j == n - 1) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }
    }
    while (!queue.isEmpty()) {
        int[] dirs = queue.poll();
        int x = dirs[0];
        int y = dirs[1];
        if (x > 0 && grid[x - 1][y] == 1) {//上
            grid[x - 1][y] = 0;
            queue.offer(new int[]{x - 1, y});
        }
        if (x < m - 1 && grid[x + 1][y] == 1) {//下
            grid[x + 1][y] = 0;
            queue.offer(new int[]{x + 1, y});
        }
        if (y > 0 && grid[x][y - 1] == 1) {//左
            grid[x][y - 1] = 0;
            queue.offer(new int[]{x, y - 1});
        }
        if (y < n - 1 && grid[x][y + 1] == 1) {//右
            grid[x][y + 1] = 0;
            queue.offer(new int[]{x, y + 1});
        }
    }

    //第二次遍历，统计矩阵中1的个数
    int res = 0;
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            //如果是1就加1
            if (grid[i][j] == 1)
                res++;
        }
    }
    return res;
}