Question ：

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

Anwser 1 ：

DFS

class Solution {
public:
    void DFS(vector<vector<char> > &board, int i, int j){
        if(i >= board.size() || j >= board[0].size()) return;
        
        if(board[i][j] == 'O'){
            board[i][j] = '#';
        
            DFS(board, i-1, j);  // to left
            DFS(board, i+1, j);  // to right
            DFS(board, i, j-1);  // to up
            DFS(board, i, j+1);  // to down
        }
    }

    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(board.empty()) return;
        
        int len = board[0].size();  // one row length
        
        for(int i = 1; i < len - 1; i++){
            DFS(board, i, 0);        // left
            DFS(board, i, len-1);    // right
        }
        
        for(int j = 0; j < len; j++){
            DFS(board, 0, j);        // up
            DFS(board, len-1, j);    // down
        }
        
        //change 'O' to 'X'
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

Anwser 2 ：

BFS

class Solution {
public:
    void enQ(vector<vector<char>> &board, int row, int col, int len, queue<int> &qu){
        if(row < 0 || row >= len || col < 0 || col >= len) return;
        if(board[row][col] == 'O'){
            board[row][col] = '#';
            qu.push(row * len + col);
        }
    }

    void BFS(vector<vector<char> > &board, int row, int col, int len, queue<int> &qu){
        enQ(board, row, col, len, qu);
        
        while(!qu.empty()){
            int val = qu.front();
            qu.pop();
            
            int row = val / len;
            int col = val % len;
        
            BFS(board, row-1, col, len, qu);  // to left
            BFS(board, row+1, col, len, qu);  // to right
            BFS(board, row, col-1, len, qu);  // to up
            BFS(board, row, col+1, len, qu);  // to down
        }
    }

    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if(board.empty()) return;
        
        int len = board[0].size();  // one row length
        queue<int> Q;
        
        for(int i = 1; i < len - 1; i++){
            BFS(board, i, 0, len, Q);        // left
            BFS(board, i, len-1, len, Q);    // right
        }
        
        for(int j = 0; j < len; j++){
            BFS(board, 0, j, len, Q);        // up
            BFS(board, len-1, j, len, Q);    // down
        }
        
        //change 'O' to 'X'
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }
};

Anwser 3 ：   BFS  in

Java

public class Solution {
    int m,n;
    char[][] board;
    Queue<Integer> queue=new LinkedList<Integer>();
    
    void fill(int x, int y){
        if(x<0 || x>=m || y<0 || y>=n || board[x][y]!='O') return;
        queue.offer(x*m+y);
        board[x][y]='D';
    }
    
    void bfs(int x, int y){
        fill(x,y);
        
        while(!queue.isEmpty()){
            int curr=queue.poll();
            int i=curr/n;
            int j=curr%n;
            
            fill(i-1,j);
            fill(i+1,j);
            fill(i,j-1);
            fill(i,j+1);
        }
    }
    
    public void solve(char[][] board){
        if(board==null || board.length==0) return;
        this.board=board;
        m=board.length;
        n=board[0].length;
        
        for(int j=0;j<n;j++){
            bfs(0,j);
            bfs(m-1,j);
        }
        
        for(int i=1;i<m-1;i++){
            bfs(i,0);
            bfs(i,n-1);
        }
        
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(board[i][j]=='O') board[i][j]='X';
                else if(board[i][j]=='D') board[i][j]='O';
            }
    }
}

注意点：

1） 方法1通过，方法2不通过，方法3有时通过有时不通过（不通过与方法2编译错误一致）

2） 查了int在c++和java中类型，int在c++两个字节，在java占四个字节，这可能会导致push（int）值过大，但在方法2（c++）中把int改为long（4字节），编译仍不通过

3）

上面这个问题研究了很长一段时间，目前还没搞明白，大家看到这篇博客欢迎来探讨、指正

参考推荐：

Leetcode 130: Surrounded Regions

Surrounded Regions