[LintCode] Surrounded Regions

Labradors 發布于2019-08-14 15:11 / 3108人閱讀

摘要：先用處理左右邊界上的換成再用處理上下邊界除去四角的換成把剩下的沒有被處理過，也就是被包圍的置為把所有暫時置為的不被包圍的換回如當前字符的坐標越界不是，返回是的都置為，然后迭代其上下左右各點

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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