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全部变成X即可。
可以利用深度优先遍历,也可以用广度优先遍历。广度优先时,当碰到O的结点就将这个坐标加入到栈中。
深度优先遍历:
//深度优先 class Solution { public: void solve(vector<vector<char>> &board) { if(board.size() == 0 || board[0].size() == 0) return ; m = board.size(); n = board[0].size(); for(int i = 0;i < n;i++){ traverse(0,i,board); traverse(m-1,i,board); } for(int i = 0;i < m;i++){ traverse(i,0,board); traverse(i,n-1,board); } for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ board[i][j] = board[i][j] == 'Z' ? 'O' : 'X'; } } } // void traverse(int x,int y,vector<vector<char>> &board){ if(x>=0 && x < m && y>=0 && y<n && board[x][y]=='O'){ board[x][y] = 'Z'; //将要保留的值赋一个额外的参数,更容易判断 traverse(x-1,y,board); //有了入口条件,就随便上下左右递归,不用担心越界问题 traverse(x+1,y,board); traverse(x,y-1,board); traverse(x,y+1,board); } } private: int m,n; };
广度优先遍历
//广度优先 class Solution { public: void solve(vector<vector<char>> &board) { if(board.size() == 0 || board[0].size() == 0) return ; m = board.size(); n = board[0].size(); for(int i = 0;i < n;i++){ if(board[0][i] == 'O') traverse(0,i,board); if(board[m-1][i] == 'O') traverse(m-1,i,board); } for(int i = 0;i < m;i++){ if(board[i][0] == 'O') traverse(i,0,board); if(board[i][n-1] == 'O') traverse(i,n-1,board); } for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ board[i][j] = board[i][j] == 'Z' ? 'O' : 'X'; } } } void add(int x,int y,vector<vector<char>> &board){ if(x>=0 && x < m && y>=0 && y<n && board[x][y]=='O'){ q.push(x*n+y); board[x][y] = 'Z'; } } void traverse(int x,int y,vector<vector<char>> &board){ add(x,y,board); while(!q.empty()){ //利用队列,来实现层序遍历 int p = q.front(); q.pop(); x = p/n; y = p%n; add(x-1,y,board); //递归向栈中加入字符为‘O’的字符 add(x+1,y,board); add(x,y-1,board); add(x,y+1,board); } } private: queue<int> q; int m,n; };