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"的 connected component，因此直覺上來說就是遍歷整個二維陣列然後以每個 "O" 作為起點去將 connected component 找出來，這樣暴力法的時間複雜度就會來到 O(n^3logn)左右。不過這題有個假設，就是只找"不連到邊界的 O"形成的 connected component，因此這邊有一個小 trick 就是我們只將邊界上的 "O" 作為起點做 BFS，其餘的不連到邊界的 "O" 就可以直接當作都被 "X" 包圍直接替換掉就好了，當 board 很大的時候，邊界上的"O"個數會遠小於不在邊界上的"O"的個數，因此這樣可以大幅降低運用 BFS 的次數。
完整程式碼:
class Solution {
public:
bool inBoard(int row, int col, int n_row, int n_col) {
return row >= 0 && row < n_row && col >= 0 && col < n_col;
}
void solve(vector<vector<char>>& board) {
if (board.empty()) { return; }
const int row_move[4] = {0, 0, 1, -1};
const int col_move[4] = {1, -1, 0, 0};
const int n_row = board.size();
const int n_col = board[0].size();
queue<pair<int, int>> q;
for (int j = 0; j < n_col; j++) {
if (board[0][j] == 'O') {
q.push(pair<int, int>{0, j});
}
if (board[n_row - 1][j] == 'O') {
q.push(pair<int, int>{n_row - 1, j});
}
}
for (int i = 0; i < n_row; i++) {
if (board[i][0] == 'O') {
q.push(pair<int, int>{i, 0});
}
if (board[i][n_col - 1] == 'O') {
q.push(pair<int, int>{i, n_col - 1});
}
}
while (!q.empty()) {
int q_size = q.size();
for (int i = 0; i < q_size; i++) {
auto cur = q.front();
q.pop();
if (board[cur.first][cur.second] == '*') { continue; }
board[cur.first][cur.second] = '*';
for (int j = 0; j < 4; j++) {
auto neighbor = pair<int, int>{cur.first + row_move[j], cur.second + col_move[j]};
if (inBoard(neighbor.first, neighbor.second, n_row, n_col)) {
if (board[neighbor.first][neighbor.second] == 'O') {
q.push(neighbor);
}
}
}
}
}
for (int i = 0; i < n_row; i++) {
for (int j = 0; j < n_col; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
for (int i = 0; i < n_row; i++) {
for (int j = 0; j < n_col; j++) {
if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
return;
}
};
沒有留言:
張貼留言