菜鸟刷题之路——Q25:颜色填充

标签: 算法刷题  1024程序员节  dfs  java  leetcode  数据结构

问题:面试题 08.10. 颜色填充

问题来自leetCode。

编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。

待填充的图像用二维数组 image 表示,元素为初始颜色值。初始坐标点的横坐标为 sr 纵坐标为 sc。需要填充的新颜色为 newColor 。

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

请用新颜色填充初始坐标点的周围区域,并返回填充后的图像。
在这里插入图片描述

分析

  首先,需要将该问题转化成一个图的问题。其实还是比较容易想到的。
  问题是让我们找到和目标点相连的所有区域,很容易想到图论中的连通图。将整个image看做是一张图,即问题转化成对当前的图寻找包含给定节点的最大连通子图问题. 典型的DFS问题。

Code

class Solution {
    public int myColor = 0;
    public int newColorr = 0;
    public boolean[][] visited;
    // 寻找连通图
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        visited = new boolean[image.length][image[0].length];
        myColor = image[sr][sc];
        newColorr = newColor;
        DFS(image,sr,sc);
        return image;
    }
    public void DFS(int[][] image, int sr, int sc) {
        // 保证下标正确
        if (sc < 0 || sc >= image[0].length) return;
        if (sr < 0 || sr >= image.length) return;
        // 保证不要重复访问,否则会爆栈
        if (visited[sr][sc]) return;
        visited[sr][sc] = true;
        // 如果颜色不同就不用染色
        if (image[sr][sc] != myColor) return;
        // 向四周寻找
        DFS(image,sr,sc-1);
        DFS(image,sr,sc+1);
        DFS(image,sr-1,sc);
        DFS(image,sr+1,sc);
        image[sr][sc] = newColorr;
    }
}

结果:


在这里插入图片描述

版权声明:本文为qq_38684427原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38684427/article/details/109262734

智能推荐

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

猜你喜欢

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...

创建一个Servlet项目流程(入门)

版本 IDEA 2020.2 JDK1.8 apache-tomcat-9.0.36 项目流程 一、IDEA中新建JaveEE项目 项目起名,选择项目存放地址,点击finish创建成功 进入项目后,右键选择项目,选择add Framework Support 选择Web Application,点击OK 此时项目文件夹 在WEB-INF下创建两个目录classes和lib 按ctrl+alt+sh...

Docker部署SpringCloud ELK+RabbitMQ日志

Docker部署SpringCloud ELK+RabbitMQ日志  Im_Coder 原文:https://www.jianshu.com/p/f773f23096a9 一、效果图 image.png 二、ELK是什么? ELK由ElasticSearch、Logstash和Kiabana三个开源工具组成。 其中Elasticsearch是个开源分布式搜索引擎,它的特点有:分布式,索...