【算法】【floodfill】洪水灌溉

文章目录

  • 1. 岛屿数量
  • 2. 岛屿最大面积
  • 3. 被围绕的区域
  • 4. 太平洋大西洋水流问题
  • 5. 扫雷游戏
  • 6. 机器人的运动范围

1. 岛屿数量

👉🔗题目链接

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

几个注意点：

  1. 二维深搜，巧妙使用全局方向矩阵
  2. 状态表记录，可以不改动原表
  3. 在搜索时注意 边界值 + 条件！！！
class Solution {
public:
    vector<vector<bool>> vis;
    int m, n;

    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        vis = vector<vector<bool>>(m, vector<bool>(n));
        int count = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j] == '1' && !vis[i][j])
                {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    
    void dfs(const 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 && grid[x][y] == '1' && !vis[x][y])
            {
                dfs(grid, x, y);
            }
        }
    }
};

2. 岛屿最大面积

👉🔗题目链接

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

和上述代码雷同！仔细设计一下哪些做全局变量吧~

3. 被围绕的区域

👉🔗题目链接

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充

和上述的题目相似，但有差别！
在边界上出现的 ‘O’ 不能计入，如果还使用之前的方法，在触碰边界条件的时候回退，代码逻辑编写起来是有困难的！怎么办呢?

正着写麻烦，就反着来吧。

先解决所有边界上的值，周围一圈的值，碰到一个 ‘O’ 就深搜一下，修改成 ‘+’。再把里面的都修改成 ‘X’ 不就解决啦！

在这里插入图片描述

class Solution {
public:
    int m, n;
    
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        // 1.将外面一圈的O相连的连通块,都处理了
        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);
        }
        // 2.还原：将O都改成X，将+都改成O
        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';
            }   
    }

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    // 把与进入位置相连的块都改成+
    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);
        }
    }
};

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

👉🔗题目链接

手动翻译一下脑残的题目：给出的矩阵中，每个数字是高于海平面的高度。水可以从高处往低处流，也可以往相同高度流，矩阵边界的水都可以往海里流。按照他给出的两个海的位置，返回一系列[x, y]位置，要求这些位置上的水，既可以流向大西洋也可以流向太平洋。(图中橙色标记的格子的 index 就是满足条件的，也就是需要返回的)
在这里插入图片描述

解法1：

  • 暴力解法，对每一个格子进行判断，既能到左上，又能到右下则加入返回集合。
  • 逻辑比较好写，就是有很多重复路径，不太聪明（sos

解法2：

  • 正难则反
  • 从边界开始反推，哪些地方的水是可以流向太平洋 / 大西洋的！
  • 最后两边一汇总就是最后可以输出的结果。
class Solution {
public:
    int m, n;

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

        // 1.填充两张状态表
        for(int i = 0; i < m; i++)
        {
            // 太平洋:左
            if(!pac[i][0]) dfs(heights, i, 0, pac);
            // 大西洋:右
            if(!ath[i][n-1]) dfs(heights, i, n-1, ath);
        }
        for(int j = 0; j < n; j++)
        {
            // 太平洋: 上
            if(!pac[0][j]) dfs(heights, 0, j, pac);
            // 大西洋: 下
            if(!ath[m-1][j]) dfs(heights, m-1, j, ath);
        }

        // 2.找出重合坐标
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(pac[i][j] && ath[i][j])
                    ret.push_back(vector<int>{i,j});

        return ret;
    }

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

    void dfs(const vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& status)
    {
        status[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 && heights[x][y] >= heights[i][j] && !status[x][y])
                dfs(heights, x, y, status);
        }
    }
};

5. 扫雷游戏

👉🔗题目链接

  • ‘M’ 代表一个 未挖出的 地雷，
  • ‘E’ 代表一个 未挖出的 空方块，
  • ‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块， 数字（‘1’ 到 ‘8’）表示有多少地雷与这块已挖出的 方块相邻， ‘X’ 则表示一个 已挖出的 地雷。 给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

  • 如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
  • 如果一个 没有相邻地雷 的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
  • 如果一个 至少与一个地雷相邻 的空方块（‘E’）被挖出，修改它为数字（‘1’ 到 ‘8’ ），表示相邻地雷的数量。
  • 如果在此次点击中，若无更多方块可被揭露，则返回盘面。

👉🔗游戏链接

class Solution {
public:
    int m, n;
    int dx[8] = {0,0,1,-1,1,1,-1,-1};
    int dy[8] = {1,-1,0,0,1,-1,1,-1};
    
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size();
        n = board[0].size();
        int i = click[0];
        int j = click[1];
        
        // 是地雷
        if(board[i][j] == 'M') 
        {
            board[i][j] = 'X';
            return board;
        }
        // 不是地雷
        dfs(board, i, j);

        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] = '0' + count;
            return;
        }

        // 没有地雷
        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);
        }
    }
};

能少走两次 count_and_modify_M 的写法：

class Solution {
public:
    int m, n;
    int dx[8] = {0,0,1,-1,1,1,-1,-1};
    int dy[8] = {1,-1,0,0,1,-1,1,-1};
    
    // 求 i,j 位置一周地雷的个数，如果有地雷，则修改board
    int count_and_modify_M (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 > 0)
            board[i][j] = '0' + count;
        return count;
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size();
        n = board[0].size();
        int i = click[0];
        int j = click[1];
        
        // 是地雷
        if(board[i][j] == 'M') 
        {
            board[i][j] = 'X';
            return board;
        }

        // 是已经挖开的
        if(board[i][j] == 'B' || (board[i][j] >= '0'+ 1 && board[i][j] <= '0'+ 8))
            return board;

        // 是挨着地雷的
        if(count_and_modify_M(board, i, j) != 0)
            return board;

        // 进入递归并判断
        dfs(board, i, j);

        return board;
    }

    void dfs(vector<vector<char>>& board, int i, int j)
    {
        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' || board[x][y] == 'M') 
                && count_and_modify_M(board, x, y) == 0)
                dfs(board, x, y);
        }
    }
};

6. 机器人的运动范围

👉🔗题目链接

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

拿到题目，别被数位之和唬住了。

机器人能走的路径是连续的，这里也就是从(0,0)开始，一次深搜的事儿，数位之和只是一个边界条件嘛！

#include <vector>
#include <iostream>
using namespace std;
class Solution 
{
public:
    int m, n, k, ret = 0;
    vector<vector<bool>> vis;

    int movingCount(int threshold, int rows, int cols) 
    {
        m = rows, n = cols, k = threshold;
        vis = vector<vector<bool>>(m, vector<bool>(n));
        dfs(0, 0);
        return ret;   
    }

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

    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] && is_accessible(x, y))
                dfs(x, y);
        }
    }

    bool is_accessible(int x, int y)
    {
        int sum = 0;
        while(x)
        {
            sum += x % 10;
            x /= 10;
        }
        while(y)
        {
            sum += y % 10;
            y /= 10;
        }
        if(sum <= k)
            return true;
        return false;
    }
};

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(✿◡‿◡) 若有差错恳请留言指正~~

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

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

相关文章

查看MySQL版本的方式

查看MySQL版本的方式

文章目录 一、使用cmd输入命令行查看二、在mysql客户端服务器里查询 一、使用cmd输入命令行查看 1、打开 cmd &#xff0c;输入命令行&#xff1a; mysql --version 2、还是打开cmd&#xff0c;输入命令行&#xff1a;mysql -V (注意了&#xff0c;此时的V是个大写的V) 二、…
阅读更多...
unity之 “Allow ‘unsafe‘ code“ 在哪里。

unity之 “Allow ‘unsafe‘ code“ 在哪里。

导入unity中的代码&#xff0c;出现如下错误&#xff0c;该如何解决&#xff1f; Unsafe code may only appear if compiling with /unsafe. Enable "Allow unsafe code" in Player Settings to fix this error 解决这个问题&#xff0c;只需要设置就可以。 设置的地…
阅读更多...
深入理解计算机系统 家庭作业 2.80

深入理解计算机系统 家庭作业 2.80

/* 网上很多都没说清楚到底出题人是什么用意,用意就是既要又要,既要不溢出,又要不丢失精度.所以就分开处理,在丢失之前把丢失的部分保存下来,然后两部分算好再相加. 可以先看一下我的2.79题 用的是先乘后除 会溢出 符合题意 2.80要求的是先除后成 不会溢出 但会丢失精度 核…
阅读更多...
C++中二叉搜索树的模拟实现(二叉搜索树是map,set的底层原理)

C++中二叉搜索树的模拟实现(二叉搜索树是map,set的底层原理)

搜索二叉树 定义 搜索二叉树:左子树小于根,右子树大于根.搜索二叉树的中序序列是升序的.所以对于二叉树而言,它的左子树和右子数都是二叉搜索树 下图就是二叉搜索树 二叉搜索树的性质: 二叉搜索树的中序遍历出的数据是有序的,并且二叉树搜索树在查找某个数的时候,一般情况下…
阅读更多...
9proxy—数据采集工具全面测评

9proxy—数据采集工具全面测评

9Proxy数据采集工具Unlock the web with 9Proxy, the top residential proxy provider. Get unlimited bandwidth, affordable prices, and secure HTTPS and Socks5 configurations.https://9proxy.com/?utm_sourceblog&utm_mediumcsdn&utm_campaignyan 前言 在当今数…
阅读更多...
如何实现仿微信界面[我的+首页聊天列表+长按菜单功能+添加菜单功能]

如何实现仿微信界面[我的+首页聊天列表+长按菜单功能+添加菜单功能]

如何实现仿微信界面[我的首页聊天列表长按菜单功能添加菜单功能] 一、简介 如何实现仿微信界面[我的首页聊天列表长按菜单功能添加菜单功能] 采用 uni-app 实现&#xff0c;可以适用微信小程序、其他各种小程序以及 APP、Web等多个平台 具体实现步骤如下&#xff1a; 下载…
阅读更多...
Windows 2008虚拟机安装、安装VM Tools、快照和链接克隆、添加硬盘修改格式为GPT

Windows 2008虚拟机安装、安装VM Tools、快照和链接克隆、添加硬盘修改格式为GPT

一、安装vmware workstation软件 VMware workstation的安装介质&#xff0c;获取路径&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1AUAw_--yjZAUPbsR7StOJQ 提取码&#xff1a;umz1 所在目录&#xff1a;\vmware\VMware workstation 15.1.0 1.找到百度网盘中vmwa…
阅读更多...
【Android】App通信基础架构相关类源码解析

【Android】App通信基础架构相关类源码解析

应用通信基础架构相关类源码解析 这里主要对Android App开发时&#xff0c;常用到的一些通信基础类进行一下源码的简单分析&#xff0c;包括&#xff1a; Handler&#xff1a;处理器&#xff0c;与某个Looper&#xff08;一个线程对应一个Looper&#xff09;进行关联。用于接…
阅读更多...
【React】React hooks 清除定时器并验证效果

【React】React hooks 清除定时器并验证效果

React hooks 清除定时器并验证效果 目录结构如下useTime hookClock.tsx使用useTime hookApp.tsx显示Clock组件显示时间&#xff08;开启定时器&#xff09;隐藏时间&#xff08;清除定时器&#xff09; 总结参考 目录结构如下 useTime hook // src/hooks/common.ts import { u…
阅读更多...
亚马逊AWS永久免费数据库

亚马逊AWS永久免费数据库

Amazon DynamoDB 是一项无服务器的 NoSQL 数据库服务&#xff0c;您可以通过它来开发任何规模的现代应用程序。作为无服务器数据库&#xff0c;您只需按使用量为其付费&#xff0c;DynamoDB 可以扩展到零&#xff0c;没有冷启动&#xff0c;没有版本升级&#xff0c;没有维护窗…
阅读更多...
05-延迟任务精准发布文章

05-延迟任务精准发布文章

延迟任务精准发布文章 1)文章定时发布 2)延迟任务概述 2.1)什么是延迟任务 定时任务&#xff1a;有固定周期的&#xff0c;有明确的触发时间延迟队列&#xff1a;没有固定的开始时间&#xff0c;它常常是由一个事件触发的&#xff0c;而在这个事件触发之后的一段时间内触发…
阅读更多...
HuggingFace踩坑记录-连不上，根本连不上

HuggingFace踩坑记录-连不上，根本连不上

学习 transformers 的第一步&#xff0c;往往是几句简单的代码 from transformers import pipelineclassifier pipeline("sentiment-analysis") classifier("We are very happy to show you the &#x1f917; Transformers library.") ""&quo…
阅读更多...
Vue - 1（ 13000 字 Vue 入门级教程）

Vue - 1（ 13000 字 Vue 入门级教程）

一&#xff1a;Vue 1.1 什么是 Vue Vue.js&#xff08;通常称为Vue&#xff09;是一款流行的开源JavaScript框架&#xff0c;用于构建用户界面。Vue由尤雨溪在2014年开发&#xff0c;是一个轻量级、灵活的框架&#xff0c;被广泛应用于构建单页面应用&#xff08;SPA&#xf…
阅读更多...
golang设计模式图解——模板方法模式

golang设计模式图解——模板方法模式

设计模式 GoF提出的设计模式有23个&#xff0c;包括&#xff1a; &#xff08;1&#xff09;创建型(Creational)模式&#xff1a;如何创建对象&#xff1b; &#xff08;2&#xff09;结构型(Structural )模式&#xff1a;如何实现类或对象的组合&#xff1b; &#xff08;3&a…
阅读更多...
移动WEB开发之flex布局

移动WEB开发之flex布局

一、flex布局体验 传统布局兼容性好&#xff0c;布局繁琐&#xff0c;局限性&#xff0c;不能再移动端很好布局 flex弹性布局操作方便&#xff0c;布局极为简单&#xff0c;移动端应用广泛&#xff0c;PC端浏览器支持情况较差 建议&#xff1a;如果是PC端页面布局&#xff0…
阅读更多...
07-app端文章搜索

07-app端文章搜索

app端文章搜索 1) 今日内容介绍 1.1)App端搜索-效果图 1.2)今日内容 文章搜索 ElasticSearch环境搭建 索引库创建 文章搜索多条件复合查询 索引数据同步 搜索历史记录 Mongodb环境搭建 异步保存搜索历史 查看搜索历史列表 删除搜索历史 联想词查询 联想词的来源 联…
阅读更多...
外围极简便携式T12电烙铁（CH32X035）－第二篇

外围极简便携式T12电烙铁（CH32X035）－第二篇

文章目录 系列文章目录前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 一、工程简介 原理图&#xff1a; PCB&#xff1a; 外壳&#xff1a; BOM&#xff1a; 二、功能模块介绍 1、 |----系统初始化 0&#xff1a;填写系统初值 …
阅读更多...
推荐使用AI开源平台：搭建GA领域案件分类的自动化处理

推荐使用AI开源平台：搭建GA领域案件分类的自动化处理

引言 公安和消防机构面临着日益复杂的案件处理任务。为了提高案件管理和分派的效率&#xff0c;自然语言处理&#xff08;NLP&#xff09;和文本分类技术的应用变得尤为重要。本文将探讨如何通过自动化处理技术快速识别案件性质和关键特征&#xff0c;从而优化资源分配&#x…
阅读更多...
9Proxy，跨境电商一站式解决方案

9Proxy，跨境电商一站式解决方案

文章目录 跨境电商什么是跨境电商跨境电商的机遇跨境电商技术支撑 海外代理IP什么是海外代理IP海外代理IP的作用如何选择海外代理IP 9Proxy9Proxy的优势9Proxy的解决方案价格汇总搜索引擎优化市场调查多重核算数据抓取广告技术 价格上手体验注册登录下载安装数据采集 总结福利 …
阅读更多...
Oracle中实现一次插入多条数据

Oracle中实现一次插入多条数据

一、需求描述 在我们实际的业务场景中&#xff0c;由于单条插入的效率很低&#xff08;每次都需要数据库资源连接关闭的开销&#xff09;&#xff0c;故需要实现一次性插入多条数据&#xff0c;用以提升数据插入的效率&#xff1b; 如下图是常见的单条插入数据&#xff1a; 二…
阅读更多...
最新文章

Copyright @ 2022~2023