Surrounded Regions

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

解题思路：

这道题的含义是将所有被X包围的O置为X（向围棋那样的包围）。注意到要想某个“O”被包住，那么至少要三行三列。

我们从四个边入手，将所有与边中某个O联通的O标记为“#”，然后将非标记的“O”置为X，最后将“#”恢复成“O”。递归算法（DFS）算法的代码如下：

class Solution {
public:
    void solve(vector>& board) {
        int m = board.size();
        if(m<3){
            return;
        }
        int n = board[0].size();
        if(n<3){
            return;
        }
        for(int i=0; i>& board, int& m, int& n, int i, int j){
        if(i<0||i>=m || j<0 || j>=n){
            return;
        }
        if(board[i][j]=='O'){
            board[i][j] = '#';
            setFlag(board, m, n, i+1, j);
            setFlag(board, m, n, i-1, j);
            setFlag(board, m, n, i, j+1);
            setFlag(board, m, n, i, j-1);
        }
    }
};

但是倘若矩阵很大，就会产生错误，原因可能是递归过深会产生错误。

那么我们应该采用迭代的方法BFS

class Solution {
public:
    void solve(vector>& board) {
        //只有行列数均大于等于3才能形成包围圈
        int m = board.size();
        if(m<3){
            return;
        }
        int n = board[0].size();
        if(n<3){
            return;
        }
        queue qx;
        queue qy;
        for(int i=0; i0 && board[x-1][y]=='O'){
                qx.push(x-1);
                qy.push(y);
            }
            if(x0 && board[x][y-1]=='O'){
                qx.push(x);
                qy.push(y-1);
            }
            if(y

 
转载请注明： » [LeetCode] Surrounded Regions

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->