[leetcode题解]130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

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

Explanation:

Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

本题是个搜索题,可以使用深度优先搜索,或者广度优先搜索都可以,但是思路都是一样的,搜索的起点就是矩阵的四个边,从边上的元素开始,只要是O的,就作为搜索起点,进行搜索,把所有能到达的O全部标记为另一个标记,比如U。最后遍历整个矩阵,所有是O的都变为X,所有为U的变回O就可以了。

注意点,在广度优先搜索时要先变成U然后在入队,如果先入队,出队的时候再变,会导致有大量的元素会被重复入队,虽然最终结果是相同的,但是由于入队重复元素太多,在大规格的时候回TLE。一下为使用C++写的代码,之所以用c++是因为c++中的容器中提供了队列这种数据结构,对于广度优先搜索来说非常方便省事。

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int rows = 0;
        int cols = 0;
        int i = 0, j = 0;
        
        rows = board.size();
        if (rows == 0)
            return;
        
        cols = board[0].size();
        if (cols == 0)
            return;
        
        for (i = 0; i < rows; i++) {
            if (board[i][0] == 'O') {
                board[i][0] = 'u';
                bfs(board, i, 0, rows, cols);
            }
                
            if (board[i][cols - 1] == 'O') {
                board[i][cols - 1] = 'u';
                bfs(board, i, cols - 1, rows, cols);
            }
        }
        
        for (i = 0; i < cols; i++) {
            if (board[0][i] == 'O') {
                board[0][i] = 'u';
                bfs(board, 0, i, rows, cols);
            }
            
            if (board[rows - 1][i] == 'O') {
                board[rows - 1][i] = 'u';
                bfs(board, rows - 1, i, rows, cols);
            }
        }
        
        
        for (i = 0; i < rows; i++) {
            for (j = 0; j < cols; j++) {
                if (board[i][j] == 'u')
                    board[i][j] = 'O';
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
    
private:
    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    void bfs(vector<vector<char>>& board, int x, int y, int rows, int cols) {
        queue<int> quex;
        queue<int> quey;
        int i = 0;
        int xx = 0, yy =0;
        int nx = 0, ny = 0;
        
        quex.push(x);
        quey.push(y);
        
        while(!quex.empty()) {
            xx = quex.front();
            quex.pop();
            yy = quey.front();
            quey.pop();
            
            for (i = 0; i < 4; i++) {
                nx = xx + dir[i][0];
                ny = yy + dir[i][1];
                
                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols 
                    || board[nx][ny] == 'X'
                    || board[nx][ny] == 'u')
                    continue;
                
                board[nx][ny] = 'u';
                quex.push(nx);
                quey.push(ny);
            }
        }
    }
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]130. Surrounded Regions

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/156.html

相关文章