[LeetCode] surrounded region包围区域

63 阅读 0 评论 42 点赞

我是靠谱客的博主矮小悟空，最近开发中收集的这篇文章主要介绍[LeetCode] surrounded region包围区域，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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，遍历的时候用一个矩阵标记经过的O。最后遍历矩阵中的每一个元素，如果该元素是O，而且该元素没有被标记过，那么就把这个O替换成X。
代码如下，在我自己的电脑上好好的，但是在leetcode的服务器上有run time error。

    void solve(vector<vector<char>> &board) {
        
        if(board.size()==0)
            return;
        
        vector<bool> visited_row(board[0].size(), false);
        vector<vector<bool>> visited_mat(board.size(), visited_row);
        
        int r = 0, c = 0;
        //traverse the left-most colum
        for( ; r<board.size(); r++){
            if(board[r][c]=='O')
                DFT(r,c, board, visited_mat);
        }
        r--;
        
        //traverse the bottom row
        for( ; c<board[0].size(); c++){
            if(board[r][c]=='O')
                DFT(r,c, board, visited_mat);
        }
        c--;
        
        // traverse the right-most column
        for( ; r>=0; r--){
            if(board[r][c]=='O')
                DFT(r,c, board, visited_mat);
        }
        r++;
        
        // traverse the top row
        for( ; c>0; c--){
            if(board[r][c]=='O')
                DFT(r,c, board, visited_mat);
        }
        
        // traverse all the elements and change 'O' to 'X'
        for(r=0; r<board.size(); r++)
            for(c=0; c<board[0].size(); c++)
            {
                if(board[r][c]=='O' && visited_mat[r][c]==false)
                    board[r][c] = 'X';
            }
    }
    
    void DFT(int row, int col, vector<vector<char>> &board, vector<vector<bool>> &visited_mat)
    {// depth first traversal
        if(!visited_mat[row][col])
        {
            visited_mat[row][col] = true;
            if(row-1>=0 && board[row-1][col]=='O') 
                DFT(row-1, col, board, visited_mat);
            if(row+1<board.size() && board[row+1][col]=='O') 
                DFT(row+1, col, board, visited_mat);
            if(col-1>=0 && board[row][col-1]=='O') 
                DFT(row, col-1, board, visited_mat);
            if(col+1<board[0].size() && board[row][col+1]=='O') 
                DFT(row, col+1, board, visited_mat);
        }
        else
            return;
    }

这里有一个不需要深度遍历的算法.