【算法】网络图中的dfs



快乐的流畅：个人主页


个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

文章目录

  • 引言
  • 一、单词搜索
  • 二、黄金矿工
  • 三、不同路径 |||
  • 四、图像渲染
  • 五、岛屿数量
  • 六、岛屿的最大面积
  • 七、被围绕的区域
  • 八、太平洋大西洋水流问题
  • 九、扫雷游戏
  • 总结

引言

在二维网络图中的dfs，反而一般不需要画决策树，因为在二维图像中有时候很直观可以看出决策关系，一般为上下左右搜索。

一、单词搜索


细节：

  • dfs函数设置返回值bool，以便及时调整路线
  • 设置向量数组dx，dy
  • 设置bool数组vis，实现剪枝
  • pos设置为函数参数，方便回溯
class Solution
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[7][7];
    int m, n;
public:
    bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
    {
        if(pos == word.size()) return true;

        vis[i][j] = true;
        for(int k=0; k<4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n 
            && !vis[x][y] && board[x][y] == word[pos])
            {
                if(dfs(board, x, y, word, pos + 1)) return true;
            }
        }
        vis[i][j] = false;
        return false;
    }

    bool exist(vector<vector<char>>& board, string& word)
    {
        m = board.size(), n = board[0].size();
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(board[i][j] == word[0])
                {
                    if(dfs(board, i, j, word, 1)) return true;
                }
            }
        }
        return false;
    }
};

二、黄金矿工


细节：

  • 设置向量数组dx，dy
  • 设置bool数组vis，实现剪枝
  • sum设置为函数参数，方便回溯
class Solution
{
    int ret = 0;
    bool vis[16][16];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
public:
    void dfs(vector<vector<int>>& grid, int i, int j, int sum)
    {
        vis[i][j] = true;
        for(int k=0; k<4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n
            && !vis[x][y] && grid[x][y])
            {
                dfs(grid, x, y, sum + grid[x][y]);
            }
            else ret = max(ret, sum);
        }
        vis[i][j] = false;
    }

    int getMaximumGold(vector<vector<int>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(grid[i][j])
                {
                    dfs(grid, i, j, grid[i][j]);
                }
            }
        }
        return ret;
    }
};

三、不同路径 |||


细节：

  • 设置向量数组dx，dy
  • 设置bool数组vis，实现剪枝
  • path设置为函数参数，方便回溯
class Solution
{
    int ret = 0;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[20][20];
    int m, n, count = 0;
public:
    void dfs(vector<vector<int>>& grid, int i, int j, int path)
    {
        if(grid[i][j] == 2)
        {
            if(path + count == m * n) ++ret;
            return;
        }

        vis[i][j] = true;
        for(int k=0; k<4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n
            && !vis[x][y] && grid[x][y] != -1)
            {
                dfs(grid, x, y, path + 1);
            }
        }
        vis[i][j] = false;
    }

    int uniquePathsIII(vector<vector<int>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        int si, sj;
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(grid[i][j] == -1) ++count;
                else if(grid[i][j] == 1) 
                {
                    si = i, sj = j;
                }
            }
        }

        dfs(grid, si, sj, 1);
        return ret;
    }
};
  • 本题开始往后，是floodfill算法的练习
  • floodfill算法，本质就是寻找连通块
  • 同时floodfill算法没有回溯

四、图像渲染



细节：

  • 设置向量数组dx，dy
  • 记录baseColor, newColor
class Solution
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int baseColor, newColor;
    int m, n;
public:
    void dfs(vector<vector<int>>& image, int i, int j)
    {
        image[i][j] = newColor;
        for(int k=0; k<4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n 
            && image[x][y] == baseColor)
            {
                dfs(image, x, y);
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        if(image[sr][sc] == color) return image;

        baseColor = image[sr][sc], newColor = color;
        m = image.size(), n = image[0].size();
        dfs(image, sr, sc);
        return image;
    }
};

五、岛屿数量


细节：

  • 设置向量数组dx，dy
  • 设置bool数组vis，实现剪枝
class Solution
{
    int ret;
    bool vis[301][301];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
public:
    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 && y >= 0 && x < m && y < n
            && !vis[x][y] && grid[x][y] == '1')
            {
                dfs(grid, x, y);
            }
        }
    }

    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')
                {
                    dfs(grid, i, j);
                    ++ret;
                }
            }
        }
        return ret;
    }
};

六、岛屿的最大面积



细节：

  • 设置向量数组dx，dy
  • 设置bool数组vis，实现剪枝
class Solution
{
    int ret, sum;
    vector<vector<bool>> vis;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
public:
    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        ++sum;
        vis[i][j] = true;
        for(int k=0; k<4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n
            && !vis[x][y] && grid[x][y] == 1)
            {
                dfs(grid, x, y);
            }
            else ret = max(ret, sum);
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        vis.resize(m, vector<bool>(n));
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(!vis[i][j] && grid[i][j] == 1)
                {
                    sum = 0;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
};

七、被围绕的区域


细节：

  • 正难则反，将边界上及其相连的‘O’先全部标记起来，最后遍历矩阵，将未被标记的‘O’改成‘X’
  • 设置向量数组dx，dy
  • 设置bool数组vis，实现剪枝
class Solution
{
    vector<vector<bool>> vis;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
public:
    void dfs(vector<vector<char>>& board, 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 && y >= 0 && x < m && y < n
            && !vis[x][y] && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }

    void solve(vector<vector<char>>& board)
    {
        m = board.size(), n = board[0].size();
        vis.resize(m, vector<bool>(n));
        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(!vis[i][j] && board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

八、太平洋大西洋水流问题




思路：正难则反，水往高处流。

  • 利用两个标记数组，分别记录太平洋和大西洋的水可以流到的区域，找出标记数组重叠的部分即可。
  • 为了只用写一份dfs函数，将vis标记数组以参数的形式传递
  • 设置向量数组dx，dy
class Solution
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;
public:
    void dfs(vector<vector<int>>& heights, 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 && y >= 0 && x < m && y < n
            && !vis[x][y] && heights[x][y] >= heights[i][j])//正难则反，水往高处流
            {
                dfs(heights, x, y, vis);
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
    {
        m = heights.size(), n = heights[0].size();
        vector<vector<bool>> vis1(m, vector<bool>(n));
        vector<vector<bool>> vis2(m, vector<bool>(n));

        for(int i=0; i<m; ++i)
        {
            if(!vis1[i][0]) dfs(heights, i, 0, vis1);
            if(!vis2[i][n-1]) dfs(heights, i, n-1, vis2);
        }

        for(int j=0; j<n; ++j)
        {
            if(!vis1[0][j]) dfs(heights, 0, j, vis1);
            if(!vis2[m-1][j]) dfs(heights, m-1, j, vis2);
        }

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

九、扫雷游戏



细节：本题实际上是一道模拟题，关键是理解题意。

  • 点击位置是雷，直接改变返回
  • 不是雷，则进入dfs函数递归
  • 对于当前格子，先计算周围8个格子中雷的数量
    • 如果有雷，将当前格子改为雷的数量，返回
    • 如果无雷，将当前格子改为挖出的空方块，继续递归
  • 递归的时候，要进行8个方向的搜索，所以向量数组要存储8个方向
class Solution
{
    bool vis[51][51];
    int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
    int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};
    int m, n;
public:
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        if(board[i][j] == 'M') return;

        int count = 0;
        for(int k=0; k<8; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'M')
            {
                ++count;
            }
        }

        if(count)
        {
            board[i][j] = count + '0';
            return;
        }
        else board[i][j] = 'B';
        
        vis[i][j] = true;
        for(int k=0; k<8; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && y >= 0 && x < m && y < n && !vis[x][y])
            {
                dfs(board, x, y);
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
    {
        int ci = click[0], cj = click[1];
        if(board[ci][cj] == 'M')
        {
            board[ci][cj] = 'X';
            return board;
        }

        m = board.size(), n = board[0].size();
        dfs(board, ci, cj);
        return board;
    }
};

总结

网络图中的dfs，常用的搜索技巧，是创建向量数组dx，dy，方便简洁地用循环遍历。


真诚点赞，手有余香

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

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

相关文章

Flutter+Getx仿小米商城项目实战教程又新增了Flutter调用原生地图

Flutter+Getx仿小米商城项目实战教程又新增了Flutter调用原生地图

FlutterGetx仿小米商城项目实战教程基于Flutter3.x录制&#xff0c;课程紧贴企业需求&#xff0c;目前已完结176讲。教程所讲内容支持Android、Ios、华为鸿蒙OS&#xff0c;教程更新于2024年4月09日新增 Flutter 调用百度地图、新增Flutter充电桩项目地图实战。支持2024年3月29…
阅读更多...
【亚马逊云】注册APN账号及报考AWS认证考试说明演示

【亚马逊云】注册APN账号及报考AWS认证考试说明演示

文章目录 1. 登录AWS网站2. 注册APN账号3. 更改APN账号密码&#xff08;选&#xff09;4. 修改APN账号信息&#xff08;选&#xff09;5. 查看AWS认证情况&#xff08;选&#xff09;6. AWS认证考试报名流程7. 修改报名控制台语言版本&#xff08;选&#xff09;8. 开始报名AWS…
阅读更多...
抖音小店三大核心！掌握之后，做店岂不是手到捏来

抖音小店三大核心！掌握之后，做店岂不是手到捏来

大家好&#xff0c;我是电商喷火 做好一家抖音小店&#xff0c;并不需要太多的技术含量&#xff0c;做好这核心三点&#xff0c;起店并不难。 这三点分别是&#xff0c;选品、流量、售后 01.选品 首先&#xff0c;店铺的商品一定要和店铺的类目高度垂直&#xff0c;不要在大…
阅读更多...
多联机常见各部件功能及常见机组制冷原理图

多联机常见各部件功能及常见机组制冷原理图

一、各部件名称和主要功能 1、压缩机 压缩机根据实际系统需要&#xff0c;调整其转速达到节能目的。 2、压缩机油温加热带 在待机状态下&#xff0c;保证压缩的油温确再启动可靠性。 3、压缩机 排气 感温包 检测压缩机的排气温度&#xff0c;达到控制和保护目的。 4、高压开…
阅读更多...
关爱内向儿童：理解与支持助力成长

关爱内向儿童：理解与支持助力成长

引言 每个孩子都是独特的&#xff0c;有些孩子天生性格外向&#xff0c;善于表达&#xff0c;而有些孩子则比较内向&#xff0c;喜欢独处。内向并不是缺点&#xff0c;而是一种性格特质。然而&#xff0c;内向的孩子在社交和学习过程中可能会面临一些挑战。本文将探讨内向儿童…
阅读更多...
失而复得：揭秘删除照片恢复的技巧！

失而复得：揭秘删除照片恢复的技巧！

我们的生活与照片紧密相连。每一张照片都承载着一段独特的记忆&#xff0c;记录着我们的喜怒哀乐。然而&#xff0c;有时候我们会因为误操作、存储设备损坏或是文件管理不当而失去这些宝贵的照片。别担心&#xff01;现在&#xff0c;我们将揭示删除照片恢复的神秘面纱&#xf…
阅读更多...
反激式开关电源-8利用AP法进行变压器设计

反激式开关电源-8利用AP法进行变压器设计

变压器AP的计算 在变压器设计中&#xff0c;主要有两种方法&#xff0c;一种称为Kc法&#xff0c;这种方法也称为磁芯几何参数法&#xff0c;如果用这个方法来进行设计&#xff0c;那么我们首先要计算出磁芯的几何参数Kc值&#xff0c;在这个参数上留有一定的裕度后选取和Kc值…
阅读更多...
Github项目部署到自己的域名

Github项目部署到自己的域名

天坑&#xff0c;买的是华为的域名&#xff0c;不过新用户才一块&#xff0c;就忍了 要买个域名&#xff0c;我买的是华为的&#xff08;此处是购买地址&#xff09; 购买后去控制台&#xff0c;点击“总览”进入域名页面 点击想要修改的域名后的“管理解析” 点击快速解析&…
阅读更多...
HTML静态网页成品作业(HTML+CSS+JS)——在线购物商城网页设计制作(4个页面)

HTML静态网页成品作业(HTML+CSS+JS)——在线购物商城网页设计制作(4个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;使用Javacsript代码实现图片轮播切换&#xff0c;共有4个页面。 二、…
阅读更多...
力扣HOT100 - 300. 最长递增子序列

力扣HOT100 - 300. 最长递增子序列

解题思路&#xff1a; 动态规划 class Solution {public int lengthOfLIS(int[] nums) {if (nums.length 0) return 0;int[] dp new int[nums.length];int max 0;Arrays.fill(dp, 1);for (int i 0; i < nums.length; i) {for (int j 0; j < i; j) {if (nums[j] <…
阅读更多...
当CV遇上transformer(三)Clip模型及源码分析

当CV遇上transformer(三)Clip模型及源码分析

当CV遇上transformer(三)Clip模型及源码分析 2020年10月&#xff0c;Dosovitskiy首次将纯Transformer的网络结构应用于图像分类任务中(ViT)&#xff0c;并取得了当时最优的分类效果&#xff0c;其研究成果是Transformer完全替代标准卷积的首次尝试。随着谷歌提出ViT之后&#…
阅读更多...
FebHost：为什么企业需要注册保加利亚.BG域名？

FebHost：为什么企业需要注册保加利亚.BG域名？

在当今全球化的商业环境中&#xff0c;对于与保加利亚市场息息相关的企业而言&#xff0c;选择合适的域名至关重要。.BG域名作为企业在线身份的重要组成部分&#xff0c;提供了多重利好&#xff0c;成为业内不容忽视的战略资源。 首先&#xff0c;地域标识性强是.BG域名的一大…
阅读更多...
ClassificationPrimitive 内部原理

ClassificationPrimitive 内部原理

ClassificationPrimitive 内部原理 发明 ClassificationPrimitive的真是个天才。其原理是利用 webgl 的模板缓冲区实现。 渲染两次, 首先是绘制模板, 然后绘制真正的内容。 示意图: function createClass() {const { program, uniforms } WebGLProgram.buildPrograms(gl, …
阅读更多...
CST电磁仿真软件什么是Schematic?三维模型和电路协同仿真【小白必学教程】

CST电磁仿真软件什么是Schematic?三维模型和电路协同仿真【小白必学教程】

什么是Schematic? 使用CST Design Studio进行的各种分析&#xff01; Schematic 进行三维仿真时&#xff0c;有时需要将3D模型和电路图放在一起进行仿真分析。比如需要天线和匹配电路协同仿真&#xff0c;两者构成完整的电路图可以系统地分析In/0ut特性。按下3D工作界面下方…
阅读更多...
Spring Security实现用户认证一：简单示例

Spring Security实现用户认证一：简单示例

Spring Security实现用户认证一&#xff1a;简单示例 1 原理1.1 用户认证怎么进行和保存的&#xff1f;认证流程SecurityContext保存 2 创建简单的登录认证示例2.1 pom.xml依赖添加2.2 application.yaml配置2.3 创建WebSecurityConfig配置类2.4 测试 1 原理 Spring Security是…
阅读更多...
React 第三十八章 React 中的位运算

React 第三十八章 React 中的位运算

位运算是一种计算机编程中常用的操作&#xff0c;它直接对二进制位进行操作。二进制&#xff0c;指的就是以二为底的一种计数方式&#xff0c;常见的还有八进制、十进制、十六进制。 十进制0123456789101112131415二进制0000000100100011010001010110011110001001101010111100…
阅读更多...
【面试干货】 两个有序数组的合并排序

【面试干货】 两个有序数组的合并排序

【面试干货】 两个有序数组的合并排序 1、实现思想2、代码实现 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 1、实现思想 使用两个指针分别指向两个数组的起始位置&#xff0c;然后逐个比较两个指针所指向的元素&#xff0c;将较小的元素…
阅读更多...
【全开源】场地预定小程序支持微信小程序+微信公众号+H5

【全开源】场地预定小程序支持微信小程序+微信公众号+H5

XYvenue是基于FastAdminUniApp开发的多场馆场地预定小程序&#xff0c;提供运动场馆运营解决方案&#xff0c;适用于体育馆、羽毛球馆、兵乒球馆、篮球馆、网球馆等场馆。 功能特性 1、场馆管理 可添加多个预约场馆&#xff0c;小程序端切换场馆显示。 2、场地管理 可添加多…
阅读更多...
C语言如何删除表中指定位置的结点？

C语言如何删除表中指定位置的结点？

一、问题 如何删除链表中指定位置的结点&#xff1f; 二、解答 删除链表中指定的结点&#xff0c;就像是排好队的⼩朋友⼿牵着⼿&#xff0c;将其中⼀个⼩朋友从队伍中分出来&#xff0c;只需将这个⼩朋友的双⼿从两边松开。 删除结点有两种情况&#xff1a; &#xff08;1&am…
阅读更多...
怎么删除pdf中的某一页？五种高效删除方法

怎么删除pdf中的某一页？五种高效删除方法

怎么删除pdf中的某一页&#xff1f;PDF文件是我们在工作中经常需要处理的一类文件&#xff0c;它的格式很稳定&#xff0c;不易修改。但是&#xff0c;有时候我们可能需要对PDF文件进行编辑&#xff0c;比如删除其中的某一页。本文将为你介绍五种高效的方法&#xff0c;帮助你轻…
阅读更多...
最新文章

Copyright @ 2022~2023