资讯专栏INFORMATION COLUMN

[Leetcode] Surrounded Regions 找出被包围的区域

miguel.jiang / 1199人阅读

摘要:原题链接边缘搜索替换法复杂度时间空间思路从矩阵的四条边上的点作为起点,搜索连续的一块区域上值为的点并赋为一个临时变量。对四条边上所有点都进行过这个步骤后,矩阵内剩余的就是被包围的。

Surrounded Regions

Given a 2D board containing "X" and "O", capture all regions
surrounded by "X".

A region is captured by flipping all "O"s into "X"s in that surrounded
region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

原题链接

边缘搜索替换法 复杂度

时间 O(MN) 空间 O(MN)

思路

从矩阵的四条边上的点作为起点,搜索连续的一块区域上值为O的点并赋为一个临时变量。这里我们用BFS或DFS进行搜索。对四条边上所有点都进行过这个步骤后,矩阵内剩余的O就是被包围的O。此时再对所有点遍历一遍,将临时变量赋回O,而剩余的O则赋为X。

注意

用队列实现BFS时,赋临时变量B时要在将周边点加入队列时就赋值,减少while循环的次数,否则Leetcode会超时

代码

广度优先 BFS

public class Solution {
    public void solve(char[][] board) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if((i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1) && (board[i][j]=="O")){
                    Queue q = new LinkedList();
                    q.offer(i * board[0].length + j);
                    board[i][j] = "B";
                    while(!q.isEmpty()){
                        Integer key = q.poll();
                        int x = key / board[0].length;
                        int y = key % board[0].length;
                        if(x > 0 && board[x-1][y]=="O"){
                            q.offer((x-1) * board[0].length + y);
                            board[x-1][y] = "B";
                        }
                        if(x < board.length - 1  && board[x+1][y]=="O"){
                            q.offer((x+1) * board[0].length + y);
                            board[x+1][y] = "B";
                        }
                        if(y > 0  && board[x][y-1]=="O"){
                            q.offer(x * board[0].length + y - 1);
                            board[x][y-1] = "B";
                        }
                        if(y < board[0].length - 1  && board[x][y+1]=="O"){
                            q.offer(x * board[0].length + y + 1);
                            board[x][y+1] = "B";
                        }
                    }
                }
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j]=="O") board[i][j]="X";
                if(board[i][j]=="B") board[i][j]="O";
            }
        }
    }
}

深度优先 DFS

public class Solution {
    static class Pair {
        public int first;
        public int second;
        public Pair(int f, int s) {
            first = f;
            second = s;
        }
    }
    
    public void solve(char[][] board) {
        if(board == null || board.length == 0) {
            return ;
        }
        for(int i = 0; i < board[0].length; ++i) {
            if(board[0][i] == "O") {
                markUnflippable(board,0,i);
            }
        }
        for(int i = 0; i < board[board.length-1].length; ++i) {
            if(board[board.length-1][i] == "O") {
                markUnflippable(board,board.length-1,i);
            }
        }
        for(int i = 0 ; i < board.length; ++i) {
            if(board[i][0] == "O") {
                markUnflippable(board,i,0);
            }
        }
        for(int i =0; i < board.length; ++i) {
            if(board[i][board[i].length-1] == "O") {
                markUnflippable(board,i,board[i].length-1);
            }
        }
    
        // modify the board
        for(int i = 0; i < board.length; ++i) {
            for(int j = 0; j < board[i].length; ++j) {
                if(board[i][j] == "O") {
                    board[i][j] = "X";
                } else if(board[i][j] == "U") {
                    board[i][j] = "O";
                }
            }
        }
    }
    
    public void markUnflippable(char[][] board, int r, int c) {
        int[] dirX = {-1,0,1,0};
        int[] dirY = {0,1,0,-1};
        ArrayDeque stack = new ArrayDeque<>();
        stack.push(new Pair(r,c));
        while(!stack.isEmpty()) {
            Pair p = stack.pop();
            board[p.first][p.second] = "U";
            for(int i = 0; i < dirX.length; ++i) {
                if(p.first + dirX[i] >= 0 && p.first + dirX[i] < board.length && p.second + dirY[i] >= 0 && p.second +dirY[i] < board[p.first + dirX[i]].length && board[p.first+dirX[i]][p.second+dirY[i]] == "O") {
                    stack.push(new Pair(p.first+dirX[i],p.second+dirY[i]));
                }
            }
        }
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66156.html

相关文章

  • [LintCode] Surrounded Regions

    摘要:先用处理左右边界上的换成再用处理上下边界除去四角的换成把剩下的没有被处理过,也就是被包围的置为把所有暂时置为的不被包围的换回如当前字符的坐标越界不是,返回是的都置为,然后迭代其上下左右各点 Problem Given a 2D board containing X and O, capture all regions surrounded by X.A region is captur...

    Labradors 评论0 收藏0
  • leetcode130. Surrounded Regions

    摘要:将所有和边界相连的都标记出来。那么当我重新遍历数组的时候,剩下的则是被完全包围的。 题目要求 Given a 2D board containing X and O (the letter O), capture all regions surrounded by X. A region is captured by flipping all Os into Xs in that s...

    focusj 评论0 收藏0
  • 力扣(LeetCode)130

    摘要:题目地址题目描述给定一个二维的矩阵,包含和字母。找到所有被围绕的区域,并将这些区域里所有的用填充。示例运行你的函数后,矩阵变为解答就是找所有被围绕的区域,然后填充是轻而易举的事情。利用进行连通性构建做一个位置映射 题目地址:https://leetcode-cn.com/probl...题目描述:给定一个二维的矩阵,包含 X 和 O(字母 O)。 找到所有被 X 围绕的区域,并将这些区...

    Eminjannn 评论0 收藏0
  • Leetcode之Union-Find(并查集)

    摘要:并查集包括查询和联合,主要使用不相交集合查询主要是用来决定不同的成员是否在一个子集合之内联合主要是用来把多个子集合成一个集合的实际运用计算机网络检查集群是否联通电路板检查不同的电路元件是否联通初始化联通与检测与是否联通返回联通的数 并查集(Union-Find)包括查询(Find)和联合(Union),主要使用不相交集合(Disjoint-Sets)查询(Find)主要是用来决定不同的...

    roland_reed 评论0 收藏0
  • 【LC总结】Union Find系列(Num of Islands I&II/Graph V

    摘要:不得不说,对于这道题而言,是一种很木讷的模板。主函数按矩阵大小建立一个类进行后续操作一个结点用来连接边角不可能被围绕的一个函数对矩阵元素进行结点线性化。同理,,,在主函数中初始化后调用。 Surrounded Regions Problem Given a 2D board containing X and O (the letter O), capture all regions s...

    bergwhite 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<