130. Surrounded Regions

发表于 | 分类于

每日一题 2019 - 05 - 04

题目：

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:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
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'转为 'X' ，其实就是在做图的深度优先搜索，不过需要注意一点的是：为了节省时间，可以只对边界上且为'O'的位置进行搜索，对符合条件的'O'将其转换为'$'，对不满足要求的'O'不做处理，最后将除了为'$'外的所有位置均置为'X'，将标记为'$'位置的元素置为'0'，同时需要对该位置的上下左右同时进行搜索，要注意访问的位置不能越界与小于0；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size() == 0 || board[0].size() == 0)
        {
            return ;
        }
        int length = board.size();
        int  width = board[0].size();
        for(int i = 0 ; i < length ; i ++ )
        {
            for(int j = 0 ; j < width ; j ++ )
            {
                if(( i == 0 || i == length - 1 || j == 0 || j == width - 1 ) && board[i][j] == 'O' )
                {
                    defind(i,j,board);
                }
            }
        }
        for(int i = 0 ; i < length ; i ++ )
        {
            for(int j = 0 ; j < width ; j++ )
            {
                if(board[i][j] == '$')
                {
                    board[i][j] = 'O' ;
                } 
                else
                {
                    board[i][j] = 'X' ;
                }
            }
        }
    }
    void defind(int i ,int j , vector<vector<char>>& board)
    {
        if(board[i][j] == 'O')
        {
            board[i][j] = '$' ;
            if(i - 1 >= 0 && board[i-1][j] == 'O')
            {
                defind(i-1,j,board);
            }
            if(i + 1 < board.size() && board[i+1][j] == 'O')
            {
                defind(i+1,j,board);
            }
            if(j - 1 >= 0 && board[i][j-1] == 'O')
            {
                defind(i,j-1,board);
            }
            if(j + 1 < board[0].size() && board[i][j+1] == 'O')
            {
                defind(i,j+1,board);
            }
        }
    }
};
0%
undefined