【Floodfill算法】dfs或者bfs解决floodfill算法

1.图像渲染

图像渲染

dfs解决代码:

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    int prev;
    vector<vector<int>> ret;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        m = image.size(), n = image[0].size();
        prev = image[sr][sc];
        dfs(image, sr, sc, color);
        return image;
    }
    void dfs(vector<vector<int>>& image, int i, int j, int color)
    {
        image[i][j] = color;

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
            {
                dfs(image, x, y, color);
            }
        }
    }
};

bfs解决代码:

 

class Solution {
public:
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int prev = image[sr][sc];
        if(prev == color) return image;
        int m = image.size(), n = image[0].size();
        
        queue<PII> q;
        q.push({sr, sc});
        while(!q.empty())
        {
            auto& [a, b] = q.front();
            image[a][b] = color;
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
                {
                    q.push({x, y});
                }
            }
        }
        return image;
    }
};

2.岛屿数量

岛屿数量

dfs解决代码:

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n, ret;
    bool vis[301][301];
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    dfs(grid, i, j);    //标记联通1
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
            {
                dfs(grid, x, y);
            }
        }
    }
};

bfs解决代码:

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n, ret;
    bool vis[301][301];
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    bfs(grid, i, j);    //标记联通1
                }
            }
        }
        return ret;
    }
    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;

        while(q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1')
                {
                    q.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
};

3.岛屿的最大面积

岛屿的最大面积

dfs解决代码:

class Solution {
public:
    bool vis[51][51]; 
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    int count;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && grid[i][j] == 1)
                {
                    count = 0;
                    dfs(grid, i, j);
                    ret = max(ret, count);
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        count++;
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
            {

                dfs(grid, x, y);
            }
        }
    }
};

bfs解决代码:

class Solution {
public:
    bool vis[51][51]; 
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && grid[i][j] == 1)
                {
                    ret = max(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        int count = 0;
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;
        count++;
        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
                {
                    q.push({x, y});
                    vis[x][y] = true;
                    count++;
                }
            }
        }
        return count;
    }
};

4.被围绕的区域

被围绕的区域

dfs解决代码:

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        for(int j = 0; j < n; j++)
        {
            if(board[0][j] == 'O') dfs(board, 0, j);
            if(board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }
        for(int i = 0; i < m; i++)
        {
            if(board[i][0] == 'O') dfs(board, i, 0);
            if(board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }
        for(int i = 0; i < m; i++)  //还原
            for(int j = 0; j < n; j++)
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                else if(board[i][j] == '.')
                    board[i][j] = 'O';
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        board[i][j] = '.';
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }
};

bfs解决代码:

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        for(int j = 0; j < n; j++)
        {
            if(board[0][j] == 'O') bfs(board, 0, j);
            if(board[m - 1][j] == 'O') bfs(board, m - 1, j);
        }
        for(int i = 0; i < m; i++)
        {
            if(board[i][0] == 'O') bfs(board, i, 0);
            if(board[i][n - 1] == 'O') bfs(board, i, n - 1);
        }
        for(int i = 0; i < m; i++)  //还原
            for(int j = 0; j < n; j++)
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                else if(board[i][j] == '.')
                    board[i][j] = 'O';
    }
    void bfs(vector<vector<char>>& board, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({i, j});
        board[i][j] = '.';
        while(!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                {
                    q.push({x, y});
                    board[x][y] = '.';
                }
            }
        }
    }
};

5.太平洋大西洋水流问题

太平洋大西洋水流问题

代码:

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
        m = h.size(), n = h[0].size();
        vector<vector<bool>> pac(m, vector<bool>(n));
        vector<vector<bool>> atl(m, vector<bool>(n));
        //pac -- 太平洋
        for(int i = 0; i < m; i++) dfs(h, i, 0, pac);
        for(int j = 0; j < n; j++) dfs(h, 0, j, pac);
        //atl -- 大西洋
        for(int i = 0; i < m; i++) dfs(h, i, n - 1, atl);
        for(int j = 0; j < n; j++) dfs(h, m - 1, j, atl);
        vector<vector<int>> ret;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(pac[i][j] && atl[i][j])
                    ret.push_back({i, j});
        return ret;
    }
    void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>>& vis)
    {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j])
            {
                dfs(h, x, y, vis);
            }
        }
    }
};

6.扫雷游戏

扫雷游戏

代码:

class Solution {
public:
    int dx[8] = {0, 0, -1, -1, -1, 1, 1, 1};
    int dy[8] = {-1, 1, -1, 0, 1, -1, 0, 1};
    int m, n;
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        int x = click[0], y = click[1];
        if(board[x][y] == 'M')
        {
            board[x][y] = 'X';
            return board;
        }
        dfs(board, x, y);
        return board;
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        //统计一下周围地雷个数
        int count = 0;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
                count++;
        }

        if(count)//如果周围有地雷记录地雷数
        {
            board[i][j] = count + '0';
            return;
        }
        else//周围无地雷继续向外扩展
        {
            board[i][j] = 'B';
            for(int k = 0; k < 8; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                {
                    dfs(board, x, y);
                }
            }
        }
    }
};

7.衣橱整理

衣橱整理

代码:

class Solution {
public:
    int m, n, cnt; 
    int ret;
    bool vis[101][101];
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int wardrobeFinishing(int _m, int _n, int _cnt) {
        m = _m, n = _n, cnt = _cnt;
        dfs(0, 0);
        return ret;
    }
    void dfs(int i, int j)
    {
        ret++;
        vis[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y))
            {
                dfs(x, y);
            }
        }
    }
    bool check(int i, int j)
    {
        int sum = 0;
        while(i)
        {
            sum += i % 10;
            i /= 10;
        }
        while(j)
        {
            sum += j % 10;
            j /= 10;
        }
        return sum <= cnt;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/633205.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java并发: 锁和同步

在Java并发: 面临的挑战那一篇中我们提到锁和同步是实现并发安全(可见性/原子性)的方法之一。这一章我们来讲讲Java中的锁和同步的各种工具&#xff0c;包括: LockSupportAbstractQueuedSynchronizerJava内置的锁实现 1. LockSupport LockSupport是基于Unsafe的park/unpark实…

linux 查看java线程与linux线程关系

linux 查看占用cpu高的 java 线程 linux 排查cpu占用100%故障 ##java程序 import java.util.Scanner; public class JavaThreadIDName {public static void main(String[] args) {Thread t Thread.currentThread();t.setName("laoyoutiao");System.out.println(&…

golang创建式设计模式---工厂模式

创建式设计模式—工厂模式 目录导航 创建式设计模式---工厂模式1)什么是工厂模式2)使用场景3)实现方式4)实践案例5)优缺点分析 1)什么是工厂模式 工厂模式(Factory Method Pattern)是一种设计模式&#xff0c;旨在创建对象时&#xff0c;将对象的创建与使用进行分离。通过定义…

以太坊(2)——共识机制与挖矿算法

共识机制 ETH采用的是基于GHOST协议的共识机制 "GHOST"&#xff08;Greedy Heaviest-Observed Sub-Tree&#xff09;共识机制&#xff0c;它是以太坊使用的一种改进的区块链共识算法。GHOST共识机制旨在提高链的安全性和效率&#xff0c;通过考虑非主链区块的贡献&…

kubectl详解

文章目录 kubectl详解一、陈述式管理1、陈述式资源管理方法2、k8s相关信息查看2.1 查看版本信息2.1.1 查看资源对象简写2.1.2 查看集群信息2.1.3 配置kubectl自动补全2.1.4 查看日志 2.2 基本信息查看2.2.1 查看集群状态2.2.2 查看命名空间 2.3 命名空间操作2.3.1 查看default命…

CDN用户平台安装说明

CDN用户平台安装说明 登录管理员系统 在”系统设置” – “高级设置” – “用户节点”中点击”添加节点” 如果所示&#xff1a; 节点名称 - 可以任意填写 进程监听端口 - 启动用户节点后&#xff0c;进程所监听的端口&#xff0c;通常是HTTP 80或者HTTPS 443&#xff0c;…

html 段落与排版标记 Web前端开发技术、详细文章(例如)

段落与排版标记 网页的外观是否美观&#xff0c;很大程度上取决于其排版。在页面中出现大段的文字&#xff0c;通常采用分段进行规划&#xff0c;对换行也有极其严格的划分。本节从段落的细节设置入手&#xff0c;利用段落与排版标记自如地处理大段的文字。 段落p标记 在HTM…

Spring Cloud Gateway 网关

一. 什么是网关&#xff08;Gateway&#xff09; 网关就是一个网络连接到另一个网络的关口。 在同一个项目或某一层级中&#xff0c;存在相似或重复的东西&#xff0c;我们就可以将这些相似重复的内容统一提取出来&#xff0c;向前或向后抽象成单独的一层。这个抽象的过程就是…

Linux磁盘高级操作

RAID RAID存储系统是一种数据存储虚拟化技术&#xff0c;它将多个物理磁盘驱动器组合成一个或多个逻辑单元&#xff0c;以提供数据冗余和/或提高性能。 1. RAID 0 无奇偶校验与冗余&#xff08;磁盘容错&#xff09;的条带存储&#xff08;带区卷/条带卷&#xff09; 由两块…

Linux-文件或目录权限

在使用 ll 时&#xff0c;可以查看文件夹内容的详细信息&#xff0c;信息的第1位表示类型&#xff0c;具体信息如下&#xff1a; 类型说明-普通文件d文件夹b块设备文件c字符设备文件p管道文件s套接口文件 第2-10位表示权限&#xff0c; 举例&#xff1a;rwxr-xr-x 类型说明r…

简单快捷的图片格式转换工具:认识webp2jpg-online

经常写博客或记笔记的朋友们可能会碰到图床不支持的图片格式或图片太大需要压缩的情况。通常&#xff0c;我们会在浏览器中搜索在线图片格式转换器&#xff0c;但这些转换器往往伴有烦人的广告或要求登录&#xff0c;并且支持的转换格式有限。最近&#xff0c;我在浏览 GitHub …

java8总结

java8总结 java8新特性总结1. 行为参数化2. lambda表达式2.1 函数式接口2.2 函数描述符 3. Stream API3.1 付诸实践 java8新特性总结 行为参数化lambda表达式Stream Api 1. 行为参数化 定义&#xff1a;行为参数化&#xff0c;就是一个方法接受多个不同的行为作为参数&#x…

HiWoo Box边缘计算网关

​在数字化浪潮汹涌的今天&#xff0c;边缘计算网关成为了连接物理世界与数字世界的桥梁&#xff0c;其重要性日益凸显。HiWoo Box&#xff0c;作为一款功能强大的边缘计算网关&#xff0c;不仅具备了传统网关的基本功能&#xff0c;更在数据采集、处理、传输等方面展现出了卓越…

岛屿问题刷题

200. 岛屿数量 - 力扣&#xff08;LeetCode&#xff09; class Solution {public int numIslands(char[][] grid) {int n grid.length;//grid行数int m grid[0].length;//grid列数int res 0;for(int r 0;r<n;r){for(int c0;c<m;c){if(grid[r][c]1){dfs(grid,r,c);res…

Web Server项目实战3-Web服务器简介及HTTP协议

Web Server&#xff08;网页服务器&#xff09; 一个 Web Server 就是一个服务器软件&#xff08;程序&#xff09;&#xff0c;或者是运行这个服务器软件的硬件&#xff08;计算机&#xff09;。其主要功能是通过 HTTP 协议与客户端&#xff08;通常是浏览器&#xff08;Brow…

面试八股之MySQL篇5——主从同步原理篇

&#x1f308;hello&#xff0c;你好鸭&#xff0c;我是Ethan&#xff0c;一名不断学习的码农&#xff0c;很高兴你能来阅读。 ✔️目前博客主要更新Java系列、项目案例、计算机必学四件套等。 &#x1f3c3;人生之义&#xff0c;在于追求&#xff0c;不在成败&#xff0c;勤通…

绿色智能:AI机器学习在环境保护中的深度应用与实践案例

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…

CSS transform 三大属性 rotate、scale、translate

transform 浏览器支持定义和用法translate位移函数rotate旋转函数scale缩放函数 浏览器支持 表格中的数字表示支持该属性的第一个浏览器版本号。 紧跟在 -webkit-, -ms- 或 -moz- 前的数字为支持该前缀属性的第一个浏览器版本号。 定义和用法 transform 属性向元素应用 2D…

音视频安卓主板记录仪手持终端定制开发_基于MT6762平台解决方案

音视频安卓主板采用了基于MT6762高性能处理器芯片的设计&#xff0c;其中包括4个主频高达2.0GHz的Cortex-A53核心和4个主频1.5GHz的Cortex-A53高效聚焦核心&#xff0c;可提供无比流畅的体验。搭载Android 12操作系统&#xff0c;系统版本进行了全新的优化&#xff0c;进一步确…

新火种AI|净利润上升628%,英伟达财报说明AI热潮还将持续

作者&#xff1a;一号 编辑&#xff1a;美美 AI大潮仍未放缓&#xff0c;英伟达再次超越预期。 今天凌晨&#xff0c;全球AI算力芯片龙头&#xff0c;被称为“AI时代卖铲人”的英伟达&#xff0c;正式公布了截至2024年4月28日的2025财年第一财季财报&#xff0c;其中第一财季…