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标注出来，那么剩下的O就是要变为X的了。 所以，从矩阵各个边上的O开始进行图的遍历，入栈/队列时把相应节点值从‘O'变成其他符号（我用的是'+'）,出栈/队列时对节点四方的相邻值为'O'的节点进行讨论。 全部遍历完后，把'O'变为'X'， '+'变为'O'。 代码：

1 public class Pair { 2         int x; 3         int y; 4         Pair(int x, int y) { 5             this.x = x; 6             this.y = y; 7         } 8     } 9     public void solve(char[][] board) {10         int m=board.length;11         if(m<=2)12             return;13         int n=board[0].length;14         for(int i=0;i
     
       st = new Stack
      
       ();37         bd[i][j] = '+';38         st.push(new Pair(i,j));39         40         while(!st.isEmpty()) {41             Pair temp = st.pop();42             if(temp.x>0 && bd[temp.x-1][temp.y]=='O') {43                 bd[temp.x-1][temp.y]='+';44                 st.push(new Pair(temp.x-1, temp.y));45             }46             if(temp.y
       
        0 && bd[temp.x][temp.y-1]=='O') {55                 bd[temp.x][temp.y-1]='+';56                 st.push(new Pair(temp.x, temp.y-1));57             }58         }59     }