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

作者：okokabcd

2022 年 6 月 10 日
本文字数：1178 字
阅读完需：约 4 分钟

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

一、题目大意

标签: 搜索

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

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/292efba1ab7c475ec135b1e4b】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景