草庐IT

leetcode 130. Surrounded Regions 被围绕的区域(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 搜索

https://leetcode.cn/problems/surrounded-regions

给你一个 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 == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 为 'X' 或 'O'

二、解题思路

找联通分量问题用DFS来做，主要是细节的优化。可以从这个地方入手，任何不在边界上的O都会变成X。也可以反向思维先找没有被包围的。具体的实现思路：从边界出发，去找和边界相连的O，把它标记成一个特殊值，再把网格中其他的O标记成X，最后再把第一步标记成特殊值的O还原

三、解题方法

3.1 Java实现

public class Solution {
    public void solve(char[][] board) {
        this.m = board.length;
        if (this.m == 0) {
            return;
        }
        this.board = board;
        this.n = board[0].length;

        for (int y = 0; y < m; y++) {
            dfs(0, y);
            dfs(n - 1, y);
        }

        for (int x = 0; x < n; x++) {
            dfs(x, 0);
            dfs(x, m - 1);
        }

        Map<Character, Character> v = new HashMap<>();
        v.put('G', 'O');
        v.put('O', 'X');
        v.put('X', 'X');
        for (int y = 0; y < m; y++) {
            for (int x = 0; x < n; x++) {
                switch (board[y][x]) {
                    case 'G':
                        board[y][x] = 'O';
                        break;
                    case 'O':
                        board[y][x] = 'X';
                        break;
                    case 'X':
                        board[y][x] = 'X';
                }
            }
        }
    }

    private char[][] board;
    private int m;
    private int n;

    private void dfs(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[y][x] != 'O') {
            return;
        }
        board[y][x] = 'G';
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);
    }
}

四、总结小记

  • 2022/6/10 联通分量问题用DFS
Surroundedleetcodeboardnbsp解题算法与数据结构

有关leetcode 130. Surrounded Regions 被围绕的区域(中等)的更多相关文章

  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

随机推荐