0%

LeetCode: Surrounded Regions

DFS 会超时,因为栈太大了,只能用BFS

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
class Solution {
public:
void solve(vector<vector<char>>& board) {
int n = board.size();
if (n == 0)
return;
int m = board[0].size();
queue<pair<int, int>> q;

for (int i = 0; i < n; ++i)
{
if (board[i][0] == 'O')
q.push(pair<int, int>(i, 0));
if (board[i][m - 1] == 'O')
q.push(pair<int, int>(i, m - 1));
}
for (int j = 1; j < m - 1; ++j)
{
if (board[0][j] == 'O')
q.push(pair<int, int>(0, j));
if (board[n - 1][j] == 'O')
q.push(pair<int, int>(n - 1, j));
}

while (!q.empty())
{
auto p = q.front();
q.pop();
int x = p.first, y = p.second;
board[x][y] = '+';

if (x>0 && board[x - 1][y] == 'O')
q.push(pair<int, int>(x - 1, y));
if (x < n - 1 && board[x + 1][y] == 'O')
q.push(pair<int, int>(x + 1, y));
if (y>0 && board[x][y - 1] == 'O')
q.push(pair<int, int>(x, y - 1));
if (y < m - 1 && board[x][y + 1] == 'O')
q.push(pair<int, int>(x, y + 1));
}

for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (board[i][j] == 'O')
board[i][j] = 'X';
else if (board[i][j] == '+')
board[i][j] = 'O';

}

};