题目描述

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

思路：

比较笨的思路，使用一个boolean型的二维数组保存棋盘中的点是否应该保留O，从棋盘边缘的O开始深搜，只进入flag[x][y]=false以及board[x][y]=‘O’的点，深搜完之后遍历棋盘，把flag[x][y]=false对应的board[x][y]全部变为‘X’。

代码：

public class Solution {

    private boolean[][] flag;

    private int[][] direction = {{-1,1,0,0},{0,0,-1,1}};

    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        int width = board[0].length;
        int height = board.length;
        flag = new boolean[height][width];
        // 遍历棋盘边缘
        for (int row=0; row<height; row++){
            if (board[row][0] == 'O') findNeighbor(row, 0, board);
            if (board[row][width-1] == 'O') findNeighbor(row, width-1, board);
        }
        for (int col=0; col<width; col++){
            if (board[0][col] == 'O') findNeighbor(0, col, board);
            if (board[height-1][col] == 'O') findNeighbor(height-1, col, board);
        }
        // 修改最终棋盘
        for (int i=0; i<height; i++){
            for (int j=0; j<width; j++){
                if (flag[i][j] == false){
                    board[i][j] = 'X';
                }
            }
        }
    }
    // 深搜
    void findNeighbor(int x, int y, char[][] board){
        flag[x][y] = true;
        for (int j=0; j<direction[0].length; j++){
            int newX = x + direction[0][j];
            int newY = y + direction[1][j];
            if (newX>=0&&newX<board.length&&
                    newY>=0&&newY<board[0].length&&
                    board[newX][newY] == 'O'&&
                    !flag[newX][newY]){
                findNeighbor(newX, newY, board);
            }
        }
    }
}