[LintCode] Surrounded Regions

Labradors 发布于2019-08-14 15:11 / 3014人阅读

摘要：先用处理左右边界上的换成再用处理上下边界除去四角的换成把剩下的没有被处理过，也就是被包围的置为把所有暂时置为的不被包围的换回如当前字符的坐标越界不是，返回是的都置为，然后迭代其上下左右各点

Problem

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.

Example

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

After capture all regions surrounded by "X", the board should be:

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

Solution

public class Solution {
    public void surroundedRegions(char[][] board) {
        // Write your code here
        if (board == null || board.length < 2 || board[0].length < 2) return;
        int m = board.length;
        int n = board[0].length;
        //先用bfs处理左右边界上的"O"(换成"#")
        for (int i = 0; i < m; i++) {
            if (board[i][0] == "O") {
                bfs(board, i, 0);
            }
            if (board[i][n-1] == "O") {
                bfs(board, i, n-1);
            }
        }
        //再用bfs处理上下边界（除去四角）的"O"(换成"#")
        for (int i = 1; i < n-1; i++) {
            if (board[0][i] == "O") {
                bfs(board, 0, i);
            }
            if (board[m-1][i] == "O") {
                bfs(board, m-1, i);
            }
        }
        //把剩下的没有被处理过，也就是被包围的"O"置为"X"
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == "O") {
                    board[i][j] = "X";
                }
            }
        }
        //把所有暂时置为"#"的不被包围的"O"换回"O"
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == "#") {
                    board[i][j] = "O";
                }
            }
        }
    }
    public void bfs(char[][] board, int row, int col) {
        //如当前字符的坐标越界or不是"O"，返回
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != "O") {
            return;
        }
        //是"O"的都置为"#"，然后迭代其上下左右各点
        board[row][col] = "#";
        bfs(board, row-1, col);
        bfs(board, row+1, col);
        bfs(board, row, col-1);
        bfs(board, row, col+1);
    }
}

GPU云服务器云服务器 Regions Surrounded LintCode LintCode134_LRU

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

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

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 2019-08-16 10:45 评论0 收藏0
[Leetcode] Surrounded Regions 找出被包围的区域

摘要：原题链接边缘搜索替换法复杂度时间空间思路从矩阵的四条边上的点作为起点，搜索连续的一块区域上值为的点并赋为一个临时变量。对四条边上所有点都进行过这个步骤后，矩阵内剩余的就是被包围的。 Surrounded Regions Given a 2D board containing X and O, capture all regionssurrounded by X. A region i...

miguel.jiang 2019-08-14 16:10 评论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 2019-08-14 15:51 评论0 收藏0
Leetcode之Union-Find(并查集)

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

roland_reed 2019-08-15 13:44 评论0 收藏0
href的那些事

摘要：看个问题此时的值是什么呢带着这样的疑问，开始今天的话题的那些事。问题分析为什么会有这个问题呢上周在项目中，会对页面标签绑定些事件，会用到内容。总结写在最后，对于的事情还不完整，欢迎补充补充。看个问题test,此时href的值是什么呢？带着这样的疑问，开始今天的话题‘href的那些事’。问题分析为什么会有这个问题呢？上周在项目中，msui会对页面a标签绑定些事件，会用到href内容...

rose 2019-08-01 15:30 评论0 收藏0