leetcode_surrounded_regions

发表于

难度：Medium

解题思路：把矩阵想象成一个长方形，如果四周都是’X’,那么里面的都将包围。如果有未被包围的，一定从四周有’O’开始。

X X X X 
X X X O
X X X X
X X X X

继续观察，如果与四周的’O’相交的’O’，那么它也将不会被包围。

X X X X
X X O O    
X X X X
X X X X

继续观察，与上一个’O’相交的’O’，也不会被包围。

X X X X
X O O O
X X X X
X X X X

依次类推，可以得到解题思路：先从最外围的四周，找’O’。再从找到的’O’的上下左右，继续找’O’，直到找完为止。所有找到的’O’都不会被包围，可以直接对数组中相应位置赋予值，予以区分。寻找的过程就像病毒感染一样，所以加上了Infection的标签。实现的过程用queue。
代码如下。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size() == 0)   return;
        queue<pair<size_t,size_t>> infect_queue;
        size_t row_length = board.size();
        size_t col_length = board[0].size();
        size_t i = 0, j = 0;
        for(; j != board[0].size(); j++)
        {
            if(board[i][j] == 'O')
            {
                infect_queue.push(make_pair(i,j));
            }
        }
        i = board.size()-1;
        j = 0;
        for(; j != board[0].size(); j++)
        {
            if(board[i][j] == 'O')
            {
                infect_queue.push(make_pair(i,j));
            }
        }
        i = 0;
        j = 0;
        for(; i != board.size(); i++)
        {
            if(board[i][j] == 'O')
            {
                infect_queue.push(make_pair(i,j));
            }
        }
        i = 0;
        j = board[0].size()-1;
        for(; i != board.size(); i++)
        {
            if(board[i][j] == 'O')
            {
                infect_queue.push(make_pair(i,j));
            }
        }
        
        while(!infect_queue.empty())
        {
            auto value =  infect_queue.front();
            infect_queue.pop();
            i = value.first;
            j = value.second;
            if(board[i][j] == 'E')
            {
                continue;
            }
            else if(board[i][j] == 'O')
            {
                board[i][j] = 'E';
            }
            if(i != 0 && board[i-1][j] == 'O')
            {
                infect_queue.push(make_pair(i-1,j));
            }
            if(i != row_length - 1 && board[i+1][j] == 'O')
            {
                infect_queue.push(make_pair(i+1,j));
            }
            if(j != 0 && board[i][j-1] == 'O')
            {
                infect_queue.push(make_pair(i,j-1));
            }
            if(j != col_length - 1 && board[i][j+1] == 'O')
            {
                infect_queue.push(make_pair(i,j+1));
            }
        }

        i = 0,j = 0;
        for(;i < row_length; i++)
        {
            for(j = 0;  j < col_length; j++)
            {
                if(board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
                else if(board[i][j] == 'E')
                {
                    board[i][j] = 'O';
                }
            }
        }
    }
};

运行结果：16ms，超过52.21%