当前位置 : 主页 > 编程语言 > 其它开发 >

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

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

标签: 搜索

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
上一篇:vue传值的几种方式
下一篇:没有了
网友评论