題目

(https://leetcode.com/problems/surrounded-regions/)
給定一個(gè)二維的矩陣，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
運(yùn)行你的函數(shù)后，矩陣變?yōu)椋?/p>

X X X X
X X X X
X X X X
X O X X
解釋:

被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說，任何邊界上的 'O' 都不會(huì)被填充為 'X'。 任何不在邊界上，或不與邊界上的 'O' 相連的 'O' 最終都會(huì)被填充為 'X'。如果兩個(gè)元素在水平或垂直方向相鄰，則稱它們是“相連”的。

分析

換一個(gè)思路。從邊界開始。只要與邊界O有連接的，最后肯定是沒有被X包圍的。
從四邊開始遍歷。被O連接的地方，改成Z，然后把這個(gè)地方入棧遍歷。

四邊遍歷完后。把內(nèi)部的O都變成X。因?yàn)閮?nèi)部的O都是被X包圍的。
然后再吧Z改成O

代碼

class Solution {
    public void solve(char[][] board) {
        if (board.length>2 && board[0].length>2){
                Stack<int[]> stack = new Stack<>();
                //遍歷四邊
                for (int i = 1; i < board.length-1; i++) {
                    if (board[i][0] == 'O'){
                        if (board[i][1] == 'O'){
                            board[i][1] = 'Z';
                            int [] temp ={i,1};
                            stack.push(temp);
                        }
                    }
                    while (!stack.empty()){
                        int[] pop = stack.pop();
                        setX(board,pop,stack);
                    }
                }

                for (int i = 1; i < board.length-1; i++) {
                    if (board[i][board[0].length-1] == 'O'){
                        if (board[i][board[0].length-2] == 'O'){
                            board[i][board[0].length-2] = 'Z';
                            int [] temp ={i,board[0].length-2};
                            stack.push(temp);
                        }
                    }
                    while (!stack.empty()){
                        int[] pop = stack.pop();
                        setX(board,pop,stack);
                    }
                }

                for (int i = 1; i < board[0].length-1; i++) {
                    if (board[0][i] == 'O'){
                        if (board[1][i] == 'O'){
                            board[1][i] = 'Z';
                            int [] temp ={1,i};
                            stack.push(temp);
                        }
                    }
                    while (!stack.empty()){
                        int[] pop = stack.pop();
                        setX(board,pop,stack);
                    }
                }

                for (int i = 1; i < board[0].length-1; i++) {
                    if (board[board.length-1][i] == 'O'){
                        if (board[board.length-2][i] == 'O'){
                            board[board.length-2][i] = 'Z';
                            int [] temp ={board.length-2,i};
                            stack.push(temp);
                        }
                    }
                    while (!stack.empty()){
                        int[] pop = stack.pop();
                        setX(board,pop,stack);
                    }
                }
            }

            for (int i = 1; i < board.length-1; i++) {
                for (int j = 1; j < board[i].length-1; j++) {
                    if (board[i][j] == 'O'){
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == 'Z'){
                        board[i][j] = 'O';
                    }

                }
            }
    }
    
    
    private  void setX(char[][] board,int[] pop, Stack<int[]> stack){
             //up
            if (pop[1]-1>0 && board[pop[0]][pop[1]-1] == 'O'){
                board[pop[0]][pop[1]-1] = 'Z';
                int [] temp ={pop[0],pop[1]-1};
                stack.push(temp);
            }
            //down
            if (pop[1]+1<board[0].length-1 && board[pop[0]][pop[1]+1] == 'O'){
                board[pop[0]][pop[1]+1] = 'Z';
                int [] temp ={pop[0],pop[1]+1};
                stack.push(temp);
            }

            //right
            if (pop[0]+1<board.length-1 && board[pop[0]+1][pop[1]] == 'O'){
                board[pop[0]+1][pop[1]] = 'Z';
                int [] temp ={pop[0]+1,pop[1]};
                stack.push(temp);
            }

            //left
            if (pop[0]-1>0 && board[pop[0]-1][pop[1]] == 'O'){
                board[pop[0]-1][pop[1]] = 'Z';
                int [] temp ={pop[0]-1,pop[1]};
                stack.push(temp);
            }
        }
}

結(jié)果

image.png