【题目】

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

【题意】

给定一个二维矩阵，由'X'和'O'填充，本题要求把那些被'X'包围的'O'替换为'X'。注意这里的包围是指四周全然包围。

假设某片'O'区域触及了矩阵的边界。则这片区域就不算被'X'包围。

【思路】

    我们仅仅须要先把触及到边界的'O'区域所有替换成还有一个字母, 比方'M'。矩阵中剩下的'O'区域就肯定是被包围的了。

    然后，我们扫描矩阵把'O'替换成'X'， 把'M'替换回'O'就可以

    

    区域的遍历，使用DFS或BFS

    DFS要使用递归，当矩阵非常大的时候easy超时

    所以本题使用BFS

    

【代码】

class Solution {public:    void O2M(vector
      
       
         >&board, int i, int j){        //从board[i][j]開始。遍历'O'区域，把'O'替换成'M'        int rows=board.size();        int cols=board[0].size();        queue
        
          qe;        qe.push(i*cols+j);        board[i][j]='M';        while(!qe.empty()){            int pos = qe.front(); qe.pop();            i=pos/cols;            j=pos%cols;            //推断上方            if(i-1>=0 && board[i-1][j]=='O'){                board[i-1][j]='M';  //注意在将相邻元素填到队列中时，须要将它标记为以訪问，否则以后在确定其它节点的'O'相邻位置时，非常有可能又把这个节点增加到队列中。造成死循环。                qe.push((i-1)*cols + j);            }            //推断下方            if(i+1
         
          =0 && board[i][j-1]=='O'){                board[i][j-1]='M';                qe.push(i*cols + j-1);            }            //推断右方            if(j+1
          
           > &board) {        int rows=board.size();        if(rows==0)return;        int cols=board[0].size();        if(cols==0)return;                //把临边的'O'区域替换成'M'        //上边        for(int j=0; j