LeetCode 面试题 08.10. 颜色填充（BFS）

川长思鸟来 2022-12-04 09:28 108阅读 0赞

**上一篇博客：[LeetCode 733. 图像渲染（DFS、BFS）][LeetCode 733. _DFS_BFS]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 面试题 08.10. 颜色填充][LeetCode _ 08.10.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
     *  提示
 *  题解
 *   *  解题思路
     *  解题代码
     *  时间复杂度
     *  提交结果

# 题目信息 #

## 题目描述 ##

编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。  
待填充的图像用二维数组 `image` 表示，元素为初始颜色值。初始坐标点的横坐标为 `sr` 纵坐标为 `sc`。需要填充的新颜色为 `newColor` 。

「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。

请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。

## 示例 ##

![示例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

## 提示 ##

*  `image` 和 `image[0]` 的长度均在范围 `[1, 50]` 内。
 *  初始坐标点 `(sr,sc)` 满足 `0 <= sr < image.length` 和 `0 <= sc < image[0].length`。
 *  `image[i][j]` 和 `newColor` 表示的颜色值在范围 `[0, 65535]` 内。

# 题解 #

## 解题思路 ##

本题是一个经典的 `dfs` 算法，当然本题也可以使用 `bfs` 来解决，这里只贴一下 `dfs` 的代码。首先还是和上一篇博客一样为了方便我们将 `image` 使用全局变量来存储一下，这样可以让我们再传递参数的时候少传递一个参数。还有就是为了方便 上、下、左、右 搜索，我们使用两个数组 `dx[]` 和 `dy[]` 来存储四个方向。

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

最重要的一点是不要忘了标记一下已经遍历过的位置坐标，比如我们可以将我们走过的位置标记为 `-1` ，在进行递归遍历的时候我们要判断一下当前该点是否被遍历过了，还有就是要判断一下有没有越界。

## 解题代码 ##

class Solution { 
    public:
        vector<vector<int>> img,flag;
        int dx[4] = { -1, 0, 1, 0}, dy[4] = { 0, 1, 0, -1};
    
        vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { 
            img = flag = image;
            dfs(sr, sc, newColor);
            return img;
        }
    
        void dfs(int x, int y, int newColor) { 
            int oldColor = img[x][y];
            img[x][y] = newColor;
            flag[x][y] = -1;
            for (int i = 0; i < 4; i++) { 
                int x1 = x + dx[i], y1 = y + dy[i];
                if (inmap(x1, y1) && flag[x1][y1] != -1 && img[x1][y1] == oldColor) 
                    dfs(x1, y1, newColor);
            }
        }
    
        bool inmap(int x, int y) { 
            return x >= 0 && x < img.size() && y >= 0 && y < img[x].size();
        }
    };

## 时间复杂度 ##

**O(n×m)**，其中 **n** 和 **m** 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。

## 提交结果 ##

![提交结果][20200907224926667.png]

--------------------

> 未完待续，持续更新中……  
> ![Tomcat 我们走][Tomcat]

[LeetCode 733. _DFS_BFS]: https://ac-fun.blog.csdn.net/article/details/108354981
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode _ 08.10.]: https://leetcode-cn.com/problems/color-fill-lcci/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221123/c68cd0b5e1204e658e174b4c7ca7c4b0.png
[20200907224926667.png]: /images/20221123/49ad8e738e874229b846a913a46d59cb.png
[Tomcat]: /images/20221123/a668d799237d46abb0497b76f7618f5d.png