leetcode130. Surrounded Regions

focusj 發(fā)布于2019-08-16 10:45 / 1739人閱讀

摘要：將所有和邊界相連的都標(biāo)記出來。那么當(dāng)我重新遍歷數(shù)組的時候，剩下的則是被完全包圍的。

題目要求

Given a 2D board containing "X" and "O" (the letter 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

將所有被X環(huán)繞的O區(qū)域獲取出來并轉(zhuǎn)化為X

思路與代碼

這篇題目與leetcode200. Number of Islands思路非常相近，建議毫無思路的同學(xué)先參考一下這篇博客。其實這種將區(qū)域相連的題目往往都可以使用深度優(yōu)先遍歷或者是Union-Find方法來實現(xiàn)。在這里我就給出深度優(yōu)先遍歷的實現(xiàn)方法，有興趣的同學(xué)可以參考上文的博客來自己實現(xiàn)Union-Find方法。

和leetcode200題不同，在本題中，只有被完全包圍的圖形才可以被選中與轉(zhuǎn)化，也就是，任何一個和數(shù)組邊界上的O相連的都不可能是完全包圍。所以在這題里我們采用逆向思維。將所有和邊界O相連的O都標(biāo)記出來。那么當(dāng)我重新遍歷數(shù)組的時候，剩下的O則是被完全包圍的。

代碼如下：

    public void solve(char[][] board) {
        if(board.length<=2 || board[0].length<=2 ) return;
        int row = board.length;
        int column = board[0].length;
        for(int i = 0 ; i=board.length || j>=board[0].length) return;
        if(board[i][j] == "X" || board[i][j]=="*") return;
        board[i][j] = "*";
        if(i>1 && board[i-1][j]=="O") boundarySearch(board, i-1, j);
        if(j>1 && board[i][j-1]=="O") boundarySearch(board, i, j-1);
        if(i

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~