草庐IT

Leetcode.130 被围绕的区域

感觉画质不如…原神 2023-07-09 原文

题目链接

Leetcode.130 被围绕的区域 mid

题目描述

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

示例 1：

输入：board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [[“X”]]
输出：[[“X”]]

提示：

  • m = = b o a r d . l e n g t h m == board.length m==board.length
  • n = = b o a r d [ i ] . l e n g t h n == board[i].length n==board[i].length
  • 1 < = m , n < = 200 1 <= m, n <= 200 1<=m,n<=200
  • board[i][j]为 'X'或 'O'

解法：dfs

我们先从 b o a r d board board 的四周，与边界相邻的 b o a r d [ i ] [ j ] = board[i][j] = board[i][j]= ’O'的区域记录下来，这些区域是不能被 'X'填充的。

接着，剩下的 b o a r d [ i ] [ j ] = board[i][j] = board[i][j]= ’O'的区域才是能被 'X'填充的。

时间复杂度： O ( m n ) O(mn) O(mn)

C++代码：


class Solution {
public:
    void solve(vector<vector<char>>& g) {
        int m = g.size() , n = g[0].size();
        //记录是否被访问过
        bool vis[m][n];
        memset(vis,false,sizeof vis);

        function<void(int ,int,bool)> dfs = [&](int i,int j,bool mode) -> void{
            if(i < 0 || i >= m || j < 0 || j >= n || vis[i][j]) return;
            if(g[i][j] == 'X') return;
            
            vis[i][j] = true;
            if(mode) g[i][j] = 'X';

            dfs(i + 1,j,mode);
            dfs(i - 1,j,mode);
            dfs(i,j + 1,mode);
            dfs(i,j - 1,mode);
        };
        //记录从左右两边开始的 不能被 'X' 填充的位置
        for(int i = 0;i < m;i++){
            if(g[i][0] == 'O' && !vis[i][0]) dfs(i,0,false);
            if(g[i][n-1] == 'O' && !vis[i][n-1]) dfs(i,n-1,false);
        }
        //记录从上下两边开始的 不能被 'X' 填充的位置
        for(int j = 0;j < n;j++){
            if(g[0][j] == 'O' && !vis[0][j]) dfs(0,j,false);
            if(g[m-1][j] == 'O' && !vis[m-1][j]) dfs(m-1,j,false);
        }
        //剩下的 g[i][j] == 'O' 并且没有被访问过的位置 都可以被 'X'填充
        for(int i = 1;i < m - 1;i++){
            for(int j = 1;j < n - 1;j++){
                if(g[i][j] == 'O' && !vis[i][j]) dfs(i,j,true);
            }
        }
    }
};
Leetcode130spanclasstoken深度优先算法

有关Leetcode.130 被围绕的区域的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby-on-rails - 缺失区域；使用 :region option or export region name to ENV ['AWS_REGION' ] - 2

    我知道还有其他相同的问题，但他们没有解决我的问题。我不断收到错误:Aws::Errors::MissingRegionErrorinBooksController#create,缺少区域；使用:region选项或将区域名称导出到ENV['AWS_REGION']。但是，这是我的配置开发.rb:config.paperclip_defaults={storage::s3,s3_host_name:"s3-us-west-2.amazonaws.com",s3_credentials:{bucket:ENV['AWS_BUCKET'],access_key_id:ENV['AWS_ACCE

  3. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  4. ruby - 当我已经在使用 %r 时，为什么 rubocop 要求我放置//围绕正则表达式？ - 2

    我有以下正则表达式regexp=%r{((returned|undelivered)\smail|mail\sdelivery(\sfailed)?)}x但是当我在上面运行rubocop时，它会提示我需要“在正则表达式周围使用//”。我怎样才能绕过它？ 最佳答案 您可以通过将.rubocop.yml文件添加到项目文件夹的根目录并设置适当的配置来禁用(和启用)任何rubocopcop。要查看您可以做什么，请查看rubocop包中的全局default.yml。它有完整的评论。对于这个特殊问题，创建一个.rubocop.yml和...要完

  5. ruby - 使用适用于 Ruby 的 AWS 开发工具包发布到 SNS 主题时指定区域 - 2

    我正在使用适用于Ruby的AWS开发工具包向Rails3应用程序发布消息和AWSSNS主题，如下所示:sns=AWS::SNS.newtopic=sns.topics['arn:aws:sns:eu-west-1:55555555555:my_topic']topic.publish("MESSAGE",:subject=>"SUBJECT")当我发布到“us-east-1”中的主题时，它按预期工作，但发布到“eu-west-1”区域中的主题时不起作用:AWS::SNS::Errors::InvalidParameter-Invalidparameter:TopicArn:使用AWSS

  6. ruby-on-rails - 在 Rails 3 中的区域设置更改后重定向到新域中的同一页面 - 2

    使用带有以下gem的Rails3.2.8的应用程序gem'friendly_id','~>4.0'gem'route_translator'在/config/initializers/i18n.rbTLD_LOCALES={"com"=>:en,"jobs"=>:en,"net"=>:en,"in"=>:en,"de"=>:de,"ch"=>:de,"at"=>:de,"br"=>:pt,"ar"=>:es,"cl"=>:es,"mx"=>:es}在/app/controllers/application_controller.rb中，使用前置过滤器为每个请求设置语言环境:before

  7. ruby-on-rails - 如何在 Ruby on Rails 中更改区域偏移量一段时间？ - 2

    我有一个包含时间的变量foo，比如说今天下午4点，但是时区偏移量是错误的，即它处于错误的时区。如何更改时区？当我打印它时，我得到了FriJun2607:00:00UTC2009所以没有偏移量，我想将偏移量设置为-4或东部标准时间。我希望能够将偏移量设置为Time对象的一个​​属性，但这似乎不可用？ 最佳答案 你没有明确说明你是如何获得实际变量的，但既然你提到了Time类，所以我假设你有时间使用它，我会在我的回答中提到它时区实际上是Time类的一部分(在您的情况下，时区显示为UTC)。作为Time.now响应的一部分，Time.now

  8. ruby - 如何从 DateTime 值中删除区域？ - 2

    我有这个日期时间:=>Fri,03Feb201211:52:42-0500如何删除ruby​​中的区域(-0500)？我只想要这样的东西:=>Fri,03Feb201211:52:42 最佳答案 时间总有一个区(没有区就没有意义)。您可以使用DateTime#strftime在打印时选择忽略它:now=DateTime.nowputsnow#=>2012-02-03T10:01:24-07:00putsnow.strftime('%a,%d%b%Y%H:%M:%S')#=>Fri,03Feb201210:01:24参见Time#st

  9. javascript - Highcharts 突出显示两条线之间的区域 - 2

    我有下面的图表，其中有两条线http://jsfiddle.net/gh/get/jquery/1.9.1/highslide-software/highcharts.com/tree/master/samples/highcharts/demo/line-basic/series:[{name:'Tokyo',data:[7.0,6.9,9.5,14.5,18.2,21.5,25.2,26.5,23.3,18.3,13.9,9.6]},{name:'London',data:[3.9,4.2,5.7,8.5,11.9,15.2,17.0,16.6,14.2,10.3,6.6,4.8]

  10. javascript - 如何围绕标题的前半部分包装一个类？ - 2

    我正在尝试围绕标题的前半部分或后半部分包装一个类，以便我可以使用jQuery创建更加动态和炫酷的标题。理论上我想找到句子中的所有空格并将其分成两部分。如果标题包含奇数个单词，脚本应该检测到这一点并将该类添加到最近的单词。 最佳答案 这是一个有趣的问题。我会使用方便的javascriptsplice方法。Splice可用于插入和删除数组的项目。我建议打开一个检查器并尝试我在下面写的一些例子。首先，我们将使用jQuery选择header，然后操作html内容字符串。我假设您要操作的特定标题将有一个类，并且我已经替换为“动态”:varhe

随机推荐