【递归、搜索与回溯】DFS解决FloodFill算法

一、经验总结

之前我们已经研究过了BFS解决FloodFill算法：【优选算法】BFS解决FloodFill算法-CSDN博客

DFS只是遍历顺序发生了变化，其他需要注意的点大差不差。

二、相关编程题

2.1 图像渲染

题目链接

733. 图像渲染 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

以给定的初始坐标为起点开始进行DFS，将遍历到的每个位置都修改为新的颜色值（可以防止重复遍历）。需要注意的是，如果修改前后的颜色值相同则会出现重复遍历以至于死循环的结果，所以要进行特殊处理。

编写代码

class Solution {
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n, oldcolor, newcolor;
public:
    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();
        newcolor = color, oldcolor = image[sr][sc];
        image[sr][sc] = newcolor;
        DFS(image, sr, sc);
        return image;
    }

    void DFS(vector<vector<int>>& image, int sr, int sc)
    {
        for(int i = 0; i < 4; ++i)
        {
            int x=sr+dx[i], y = sc+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && image[x][y]==oldcolor)
            {
                image[x][y] = newcolor;
                DFS(image, x, y);
            }
        }
    }
};

2.2 岛屿数量

题目链接

200. 岛屿数量 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

遍历grid数组，当遇到未访问的陆地时：

  1. 统计岛屿数量
  2. 以该位置为起点进行深度优先遍历，遍历整个连通块
  3. 将整个连通块中的所有陆地都标记为已访问

编写代码

class Solution {
    int m, n, ret;
    vector<vector<bool>> visited;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        visited.resize(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j]=='1' && !visited[i][j])
                {
                    ++ret;
                    DFS(grid, i, j);
                }
            }
        }
        return ret;
    }

    void DFS(vector<vector<char>>& grid, int r, int c)
    {
        visited[r][c] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && grid[x][y]=='1' && !visited[x][y])
            {
                DFS(grid, x, y);
            }
        }
    }
};

2.3 岛屿的最大面积

题目链接

695. 岛屿的最大面积 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

同上一题基本相同，之不过需要多添加一个变量用于统计每个岛屿的面积。最终返回岛屿的最大面积。

编写代码

class Solution {
    int m, n, ret, tmp;
    vector<vector<bool>> visited;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        visited.resize(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j]==1 && !visited[i][j])
                {
                    tmp = 0;
                    DFS(grid, i, j);
                    ret = max(tmp, ret);
                }
            }
        }
        return ret;
    }

    void DFS(vector<vector<int>>& grid, int r, int c)
    {
        ++tmp;
        visited[r][c] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && !visited[x][y])
            {
                DFS(grid, x, y);
            }
        }
    }
};

2.4 被围绕的区域

题目链接

130. 被围绕的区域 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        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 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)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }

    void DFS(vector<vector<char>>& board, int r, int c)
    {
        board[r][c] = '.';
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O')
            {
                DFS(board, x, y);
            }
        }
    }
};

2.5 太平洋大西洋水流问题

题目链接

417. 太平洋大西洋水流问题 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

  1. 统计太平洋水流：以紧邻太平洋的水域（第一行和第一列）为起点逆着水流的方向（>=）进行深度优先遍历，将DFS访问过的水域标记在pacific哈希表。
  2. 统计大西洋水流：以紧邻大西洋的水域（最后一行和最后一列）为起点逆着水流的方向（>=）进行深度优先遍历，将DFS访问过的水域标记在atlantic哈希表。
  3. 找到太平洋和大西洋水流的交集，返回结果。

编写代码

class Solution {
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    vector<vector<bool>> pacific;
    vector<vector<bool>> atlantic;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        pacific.resize(m, vector<bool>(n, false));
        atlantic.resize(m, vector<bool>(n, false));
        vector<vector<int>> ret;
        for(int i = 0; i < m; ++i)
        {
            if(!pacific[i][0]) DFS(heights, pacific, i, 0);
            if(!atlantic[i][n-1]) DFS(heights, atlantic, i, n-1);
        }
        for(int j = 0; j < n; ++j)
        {
            if(!pacific[0][j]) DFS(heights, pacific, 0, j);
            if(!atlantic[m-1][j]) DFS(heights, atlantic, m-1, j);
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(pacific[i][j] && atlantic[i][j])
                {
                    ret.push_back({i, j});
                }
            }
        }
        return ret;
    }

    void DFS(vector<vector<int>>& heights, vector<vector<bool>>& ocean, int r, int c)
    {
        ocean[r][c] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && !ocean[x][y] && heights[x][y]>=heights[r][c])
            {
                DFS(heights, ocean, x, y);
            }
        }
    }
};

2.6 扫雷游戏

题目链接

529. 扫雷游戏 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

见代码

编写代码

class Solution {
    //注意：有8个方向的向量
    int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1}; 
    int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
    int m, n;
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int sr = click[0], sc = click[1];
        if(board[sr][sc] == 'M') //点中雷直接返回
        {
            board[sr][sc] = 'X';
            return board;
        }
        m = board.size(), n = board[0].size();
        DFS(board, sr, sc);
        return board;
    }

    void DFS(vector<vector<char>>& board, int r, int c)
    {
        //统计点击位置周围的地雷数量
        int cnt = 0;
        for(int i = 0; i < 8; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M')
                ++cnt;
        }

        if(cnt == 0) //周围没有地雷，向四周继续拓展
        {
            board[r][c] = 'B';
            for(int i = 0; i < 8; ++i)
            {
                int x=r+dx[i], y=c+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='E')
                    DFS(board, x, y);
            }
        }
        else //周围有地雷，标记周围地雷的数量
            board[r][c] = cnt+'0';
    }
};

2.7 衣橱整理

题目链接

LCR 130. 衣橱整理 - 力扣（LeetCode）

题目描述

在这里插入图片描述

算法原理

略

编写代码

class Solution {
    int ret;
    int _m, _n, _cnt;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool visited[100][100];
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        _m = m, _n = n, _cnt = cnt;
        DFS(0, 0);
        return ret;
    }

    void DFS(int r, int c)
    {
        visited[r][c] = true;
        ++ret;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<_m && y>=0 && y<_n && !visited[x][y] && digit(x)+digit(y)<=_cnt)
                DFS(x, y);
        }
    }

    int digit(int num)
    {
        int sum = 0;
        while(num > 0)
        {
            sum+=num%10;
            num/=10;
        }
        return sum;
    }
};

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

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

相关文章

2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024)

2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024)

2024年先进机械电子、电气工程与自动化国际学术会议(ICAMEEA 2024) 2024 International Conference on Advanced Mechatronic, Electrical Engineering and Automation 会议地点&#xff1a;杭州&#xff0c;中国 网址&#xff1a;www.icameea.com 邮箱: icameeasub-conf.c…
阅读更多...
excel宏处理魔法代码，实现按月份统计销售额和按产品统计销售额

excel宏处理魔法代码，实现按月份统计销售额和按产品统计销售额

目录 前言第一步&#xff1a;打开文件第二步&#xff1a;选中左侧任意一个sheet双击第三步&#xff1a;粘贴 魔法代码第四步&#xff1a;点击菜单栏 运行>运行子程序和用户窗口第五步&#xff1a;切换回文件&#xff0c;我们就可以看到已经生成了月份销售额统计和产品销售额…
阅读更多...
72-UDP协议工作原理及实战

72-UDP协议工作原理及实战

#ifndef UDPCOMM_H #define UDPCOMM_H#include <QMainWindow> #include <QUdpSocket> // 用于发送和接收UDP数据报 #include <QtNetwork>QT_BEGIN_NAMESPACE namespace Ui { class udpComm; } QT_END_NAMESPACEclass udpComm : public QMainWindow {Q_OBJECT…
阅读更多...
数字孪生引领智慧校园建设新篇章

数字孪生引领智慧校园建设新篇章

一、引言 在数字化浪潮的推动下&#xff0c;教育行业正经历着一场深刻的变革。智慧校园作为现代教育的新风向&#xff0c;通过整合先进的信息技术&#xff0c;正在逐步改变传统的教学、管理与服务模式。其中&#xff0c;数字孪生技术以其独特的优势&#xff0c;为智慧校园的建…
阅读更多...
聊聊系统架构之负载均衡优化实践

聊聊系统架构之负载均衡优化实践

一、写在前面 最近在进行线上监控检查时&#xff0c;我遇到了两个超出预期的案例。首先&#xff0c;网关层的监控数据与应用实际监控数据存在不一致性&#xff0c;尤其是max有较大的差异&#xff0c;详见如下图。其次在某个应用中&#xff0c;通过httpclient请求某域名时发现只…
阅读更多...
VST3音频插件技术介绍

VST3音频插件技术介绍

一.概述 1.VST3介绍 VST3&#xff08;Virtual Studio Technology 3&#xff09;是一种音频插件格式&#xff0c;由Steinberg公司开发&#xff0c;用于在数字音频工作站&#xff08;DAW&#xff09;中使用。VST3插件可以是模拟合成器、鼓机、混响器、压缩器等多种类型的音频处理…
阅读更多...
AI在医学中神奇应用

AI在医学中神奇应用

2022年11月30日&#xff0c;可能将成为一个改变人类历史的日子——美国人工智能开发机构OpenAI推出了聊天机器人ChatGPT-3.5&#xff0c;将人工智能的发展推向了一个新的高度。2023年11月7日&#xff0c;OpenAI首届开发者大会被称为“科技界的春晚”&#xff0c;吸引了全球广大…
阅读更多...
零基础入门学用Arduino 第四部分（一）

零基础入门学用Arduino 第四部分（一）

重要的内容写在前面&#xff1a; 该系列是以up主太极创客的零基础入门学用Arduino教程为基础制作的学习笔记。个人把这个教程学完之后&#xff0c;整体感觉是很好的&#xff0c;如果有条件的可以先学习一些相关课程&#xff0c;学起来会更加轻松&#xff0c;相关课程有数字电路…
阅读更多...
【调试笔记-20240618-Windows-pnpm 更新出现 Cannot find module 问题的解决方法】

【调试笔记-20240618-Windows-pnpm 更新出现 Cannot find module 问题的解决方法】

调试笔记-系列文章目录 调试笔记-20240618-Windows-pnpm 更新出现 Cannot find module 问题的解决方法 文章目录 调试笔记-系列文章目录调试笔记-20240618-Windows-pnpm 更新出现 Cannot find module 问题的解决方法 前言一、调试环境操作系统&#xff1a;Windows 10 专业版调…
阅读更多...
内部类介绍

内部类介绍

内部类&#xff08;Inner Class&#xff09;是在另一个类的内部定义的类。它可以访问外部类的所有成员&#xff0c;包括私有成员。内部类有两种主要形式&#xff1a;局部内部类&#xff08;定义在方法内部&#xff09;和成员内部类&#xff08;定义在类的内部&#xff0c;但不在…
阅读更多...
echart在线图表demo下载直接运行

echart在线图表demo下载直接运行

echart 全面的数据可视化图表解决方案 | 折线图、柱状图、饼图、散点图、水球图等各类图表展示 持续更新中 三色带下表题速度仪表盘 地图自定义图标 动态环形图饼状图 动态水波动圆形 多标题指针仪表盘 温度仪表盘带下标题 横向柱状图排名 环形饼状图 双折线趋势变化
阅读更多...
Git的3个主要区域

Git的3个主要区域

一般来说&#xff0c;日常使用只要记住下图6个命令&#xff0c;就可以了。但是熟练使用&#xff0c;恐怕要记住60&#xff5e;100个命令。 下面是我整理的常用 Git 命令清单。几个专用名词的译名如下。 Workspace&#xff1a;工作区 Index / Stage&#xff1a;暂存区 Reposito…
阅读更多...
学会这几点，轻松制作引人入胜的电子期刊

学会这几点，轻松制作引人入胜的电子期刊

随着数字化时代的到来&#xff0c;电子期刊已经成为了信息传播的重要载体。它以方便快捷、形式多样、互动性强等特点&#xff0c;受到了广泛的欢迎。那么&#xff0c;如何制作一份引人入胜的电子期刊呢&#xff1f;下面就来为大家分享几点制作电子期刊的小技巧。 1.选择合适的制…
阅读更多...
制造业为什么需要ERP企业管理软件？

制造业为什么需要ERP企业管理软件？

如今&#xff0c;传统的制造业管理方式逐渐变得力不从心~库存积压、生产效率低下、供应链混乱…想象一下&#xff0c;如果你的企业仍然依赖于手工记录订单、库存和财务数据&#xff0c;那么每当市场发生变动时&#xff0c;你就需要花费大量的时间和精力去重新调整生产计划、更新…
阅读更多...
Qt 实战（5）布局管理器 | 5.2、深入解析Qt布局管理器

Qt 实战（5）布局管理器 | 5.2、深入解析Qt布局管理器

文章目录 一、深入解析Qt布局管理器1、为什么要使用布局管理器&#xff1f;2、布局管理器类型3、布局管理器用法详解3.1、QBoxLayout&#xff08;垂直与水平布局&#xff09;3.2、QGridLayout&#xff08;网格布局&#xff09;3.3、QFormLayout&#xff08;表单布局&#xff09…
阅读更多...
LLM2Vec论文阅读笔记

LLM2Vec论文阅读笔记

这是篇LLM论文&#xff0c;用decoder-like的LLM去提取embedding文章认为&#xff0c;decoder-like的LLM在text embedding task表现不优的一大原因就是其casual attention mechanism&#xff0c;其实就是mask的问题。所以只要对现有的decoder-only LLM进行如下三步改进&#xff…
阅读更多...
接口联调测试

接口联调测试

在我们工作过程中&#xff0c;有时需要一些接口进行联调。接口联调测试&#xff0c;就是按照业务要求&#xff0c;把接口进行组合测试。接口组合起来才能实现完整的业务&#xff0c;体现更大的价值。 接口联调测试业务分析&#xff1a; 原因&#xff1a; 项目中的接口是多个…
阅读更多...
【数据结构与算法】最小生成树

【数据结构与算法】最小生成树

文章目录 最小生成树&#xff08;MST&#xff09;定义 构造最小生成树Prim算法Kruskal算法 最小生成树&#xff08;MST&#xff09; 连通图的生成树包含图的所有顶点&#xff0c;并且只含有尽可能少的边。对于生成树来说&#xff0c;若砍去它的一条边&#xff0c;则会使生成树…
阅读更多...
DOOPRIME：日本央行7月加息与否取决于数据，购债规模调整无强烈信号

DOOPRIME：日本央行7月加息与否取决于数据，购债规模调整无强烈信号

摘要 日本央行行长植田和男近日在议会发言中表示&#xff0c;7月份是否加息将取决于经济数据表现&#xff0c;而购买日本国债与加息是两个独立的问题&#xff0c;不会通过削减购债规模来释放强烈的政策信号。这一表态引发了市场的广泛关注&#xff0c;投资者和经济学家对此进行…
阅读更多...
【elementui源码解析】如何实现自动渲染md文档-第四篇

【elementui源码解析】如何实现自动渲染md文档-第四篇

目录 1.前言 2.md-loader - index.js 1&#xff09;md.render() 2&#xff09;定义变量 3&#xff09;while stripTemplate stripScript genInlineComponentText 4&#xff09;pageScript 5&#xff09;return 6&#xff09;demo-block 3.总结 所有章节&#x…
阅读更多...
最新文章

Copyright @ 2022~2023