FloodFill算法---BFS

目录

一、前言

二、算法模板套路

2.1 创建所需的全局变量：

2.2 BFS模板：

2.3 细节处理：

三、例题练习

3.1 例题1：图像渲染

3.2 例题2：岛屿数量

3.3 例题3：岛屿的最大面积

3.4 例题4：被围绕的区域

---

一、前言

在这之前我们已经学习了如何使用 DFS 解决 FloodFill 算法，如果有友友对 FloodFill 算法不太熟悉的话可以先看看我之前写的文章：FloodFill算法---DFS。里面详细介绍了什么是FloodFill算法和如何使用DFS来解决。通常 FloodFill 算法使用 DFS 或者 BFS 都可以，DFS 的代码会简洁一些，但是 BFS 可以用来解决最短路问题和拓扑排序。所以本文章可以说是为了后续使用 BFS 解决最短路问题和拓扑排序打下基础。

• 关于BFS的遍历特性：若初始点为左上角，遍历特性如下图所示。

二、算法模板套路

2.1 创建所需的全局变量：

最好设置为静态，因为非静态只有在leetcode上才行，在竞赛中都是要我们自己写Main类的因为main是静态方法所以在方法外面的全局变量要设置为静态的才能被main方法调用。

static boolean[][] vis;//（ 不一定要有）
 
static int[ ] dx = {0 , 0 , 1 , -1 };
 
static int[ ] dy = {1 , -1 , 0 , 0 };

• vis这个布尔类型数组来标记我们已经走过的路，防止重复走导致死循环：

还有一种可以不用创建 vis 来标记，直接修改原来数据的值，这个如果是在面试的时候要问一下面试官，原来数组的数值是否可以修改。

• 利用dx，dy 来实现上下左右移动（如果是8个方向的也行）：

for(int k = 0;k < 4;k++){
    int x = i + dx[k];
    int y = j + dy[k];
}

 如果是 8 个方向的话可以先画出下图。

在把黄色对应的8个位置写入到dx和dy中。例如：

下面这个例子是从上到下，从左到右写的。

static int[] dx = {-1,-1,-1,0,0,1,1,1};
static int[] dy = {-1,0,1,-1,1,-1,0,1};

2.2 BFS模板：

我们利用 int[ ]来存储坐标。

• 至于要不要回溯，要根据题目要求什么来进行决定。

• x >= 0 && x < n && y >= 0 && y < m 这个可以说是默写了，因为这就是防止越界，每道题目都是这么写的。

public void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { i, j });
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            vis[a][b] = true;///1
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]){
                    queue.add(new int[]{x,y});
                    vis[x][y] = true;///2
                }
            }
        }
    }

2.3 细节处理：

不知道大家有没有注意到在模板那里，我在代码里标记了1和2，现在我要问问友友们，2处的代码能否省略？

答：不能省略。因为如果不加上代码2的话，有些节点会重复进入，导致代码超时（这个要想清楚，因为我当时没有代码2，检查代码检查半天才找到