BFS 实现 FloodFill 算法及经典题目解析

一、FloodFill 算法简介

FloodFill 算法可以理解为根据洪水蔓延，以点覆面，在这个过程中对涉及的一些问题进行求解。

二、733. 图像渲染

题目描述：给定一个二维数组和一个指定值，当该位置上下左右四个方向初始值相同，就改为指定值（被填充），依次类推下去，直到全部感染或者无法继续。

解题思路：

• 利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。
• 也就是我们使用一个队列，记录下来所有母体，出去一个母体，就将能传染的四个位置记录进队列。
• 注意下标问题，和当全部颜色都相同时，会超出时间限制，单独处理。

解题代码：

//时间复杂度：O(N)
//空间复杂度：O(N)
import java.util.*;
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        //记录开始颜色
        int pre = image[sr][sc];
        //实例二排除
        if (pre == color) return image;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr, sc});
        //对队列进行操作，直到空
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            //下标合法且颜色相同，传染，记录上下左右
            if (x >= 0 && x < image.length && y >= 0 && y < image[0].length && pre == image[x][y]) {
                image[x][y] = color;
                queue.add( []{x - , y});
                queue.add( []{x + , y});
                queue.add( []{x, y - });
                queue.add( []{x, y + });
            }
        }
         image;
    }
}