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 XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X

 

思路：

反向思考，先找到没有被包围的区域，标记为‘+’,再把标为‘+’的区域标为‘O',标为’O'的区域改为‘X'。没有被包围的区域一定是与最外圈的’O'相连的区域，所以要先遍历区域的上下左右边界，找到‘O'的地方。接下来的问题是如何把所有与最外层‘O'相连的区域标记上。有两种思路：BFS和DFS。

所谓BFS是指把当前标记位置的上下左右都标记一遍，然后再标记相邻点的上下左右位置。不需递归，用队列。

DFS是指把当前标记位置的向一个方向标记，比如一直向左，直到没有可标记的，再换一个方向。需要递归。

代码里面BFS可以通过，DFS栈溢出了。

void solve(vector
     
      
       > &board) {        if(board.size() == 0) return;        int rowNum = board.size();        int colNum = board[0].size();        //遍历最外面一圈，找‘O'        //最上        for(int j = 0; j < colNum; j++)        {            if(board[0][j] == 'O')                BFS(board, 0, j);        }        //最下        for(int j = 0; j < colNum; j++)        {            if(board[rowNum - 1][j] == 'O')                BFS(board, rowNum - 1, j);        }        //最左        for(int i = 0; i < rowNum; i++)        {            if(board[i][0] == 'O')                BFS(board, i, 0);        }        //最右        for(int i = 0; i < rowNum; i++)        {            if(board[i][colNum - 1] == 'O')                BFS(board, i, colNum - 1);        }        for(int i = 0; i < rowNum; i++)        {            for(int j = 0; j < colNum; j++)            {                if(board[i][j] == 'O')                    board[i][j] = 'X';                if(board[i][j] == '+')                    board[i][j] = 'O';            }        }            }    void DFS(vector
       
        
         > &board, int r, int c)    {        if(r >= 0 && c >= 0 && r < board.size() && c < board[0].size() && board[r][c] == 'O')        {            board[r][c] = '+';            DFS(board, r - 1, c);            DFS(board, r + 1, c);            DFS(board, r, c - 1);            DFS(board, r, c + 1);        }    }    void BFS(vector
         
          
           > &board, int r, int c) { queue
           
            
             > q; q.push(make_pair(r, c)); while(!q.empty()) { int i = q.front().first; int j = q.front().second; q.pop(); if(i >= 0 && j >= 0 && i < board.size() && j < board[0].size() && board[i][j] == 'O') { board[i][j] = '+'; q.push(make_pair(i - 1, j)); q.push(make_pair(i + 1, j)); q.push(make_pair(i, j - 1)); q.push(make_pair(i, j + 1)); } } }
            
           
          
         
        
       
      
     

 

上面的代码已经是优化过的了，我自己写的时候只写出了DFS的，而且自己也没有意识到是DFS。代码也很繁琐。注意通过把判断条件放在一起来简化代码。

我原本很挫的代码：栈溢出。

class Solution {public:    void solve(vector
     
      
       > &board) {        if(board.size() == 0) return;        int rowNum = board.size();        int colNum = board[0].size();        //遍历最外面一圈，找‘O'        //最上        for(int j = 0; j < colNum; j++)        {            if(board[0][j] == 'O')            {                board[0][j] = '+';                mySolve(board, 0, j);            }        }        //最下        for(int j = 0; j < colNum; j++)        {            if(board[rowNum - 1][j] == 'O')            {                board[rowNum - 1][j] = '+';                mySolve(board, rowNum - 1, j);            }        }        //最左        for(int i = 0; i < rowNum; i++)        {            if(board[i][0] == 'O')            {                board[i][0] = '+';                mySolve(board, i, 0);            }        }        //最右        for(int i = 0; i < rowNum; i++)        {            if(board[i][colNum - 1] == 'O')            {                board[i][colNum - 1] = '+';                mySolve(board, i, colNum - 1);            }        }        for(int i = 0; i < rowNum; i++)        {            for(int j = 0; j < colNum; j++)            {                if(board[i][j] == 'O')                    board[i][j] = 'X';                if(board[i][j] == '+')                    board[i][j] = 'O';            }        }            }    void mySolve(vector
       
        
         > &board, int r, int c)    {        if(r - 1 >= 0 && board[r - 1][c] == 'O') //上        {            board[r - 1][c] == '+';            mySolve(board, r - 1, c);        }        if(r + 1 < board.size() && board[r + 1][c] == 'O') //下        {            board[r + 1][c] == '+';            mySolve(board, r + 1, c);        }        if(c - 1 >= 0 && board[r][c - 1] == 'O') //左        {            board[r][c - 1] == '+';            mySolve(board, r, c - 1);        }        if(c + 1 < board[0].size() && board[r][c + 1] == 'O') //下        {            board[r][c + 1] == '+';            mySolve(board, r, c + 1);        }    }};