Surrounded Regions.txt

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

---------------------------------------------------------------
这题关键在于理解题意，被包围住的'O'意思是没有一条路径使其从上、下、左、右四个方向走出棋盘格
思路：
step1 扫棋盘四条边界，若为'O'则标记为'#'，并从这点开始dfs搜索此路径上的棋子
step2 扫描整个棋盘格，若为'O'则置为'X'
step3 扫描整个棋盘格，若为'#'则置回'O'

class Solution {
public:
    void change(vector<vector<char> > &board, int x, int y)
    {
        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size())
            return;
        if(board[x][y] == 'O')
            {
                board[x][y] = '#';
                change(board, x - 1, y);
                change(board, x + 1, y);
                change(board, x, y - 1);
                change(board, x, y + 1);
            }
    }
    
    void solve(vector<vector<char>> &board) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(board.empty())
            return;
        for(int i = 0; i < board[0].size(); ++i)
            change(board, 0, i);
        for(int i = 0; i < board[0].size(); ++i)
            change(board, board.size() - 1, i);
        for(int i = 1; i < board.size() - 1; ++i)
            change(board, i, 0);
        for(int i = 1; i < board.size() - 1; ++i)
            change(board, i, board[0].size() - 1);
        for(int i = 0; i < board.size(); ++i)
            for(int j = 0; j < board[0].size(); ++j)
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
        for(int i = 0; i < board.size(); ++i)
            for(int j = 0; j < board[0].size(); ++j)
                if(board[i][j] == '#')
                    board[i][j] = 'O';
    }
};