摘要：原題鏈接邊緣搜索替換法復(fù)雜度時(shí)間空間思路從矩陣的四條邊上的點(diǎn)作為起點(diǎn)，搜索連續(xù)的一塊區(qū)域上值為的點(diǎn)并賦為一個(gè)臨時(shí)變量。對(duì)四條邊上所有點(diǎn)都進(jìn)行過這個(gè)步驟后，矩陣內(nèi)剩余的就是被包圍的。

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

原題鏈接

時(shí)間 O(MN) 空間 O(MN)

從矩陣的四條邊上的點(diǎn)作為起點(diǎn)，搜索連續(xù)的一塊區(qū)域上值為O的點(diǎn)并賦為一個(gè)臨時(shí)變量。這里我們用BFS或DFS進(jìn)行搜索。對(duì)四條邊上所有點(diǎn)都進(jìn)行過這個(gè)步驟后，矩陣內(nèi)剩余的O就是被包圍的O。此時(shí)再對(duì)所有點(diǎn)遍歷一遍，將臨時(shí)變量賦回O，而剩余的O則賦為X。

用隊(duì)列實(shí)現(xiàn)BFS時(shí)，賦臨時(shí)變量B時(shí)要在將周邊點(diǎn)加入隊(duì)列時(shí)就賦值，減少while循環(huán)的次數(shù)，否則Leetcode會(huì)超時(shí)

廣度優(yōu)先 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";
            }
        }
    }
}

深度優(yōu)先 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]));
                }
            }
        }
    }
}