這題的直觀做法就是直接從邊界的 O 開始搜尋，只有跟這些 O 相連的 O 才能保留，剩下的就都是 X。如果不用 in-place 的話，直接創造一個新的 matrix，裡面都是 X，只有在原本的 matrix 中遇到要保留的 O 才把新 matrix 中相對應的位置設成 O。
還有一個比較節省空間的做法是，如果是 valid 的 O，那就先把 char 設成另一個 char，例如 #，最後完整看過一次 matrix，如果遇到 O 就要變成 X，遇到 # 才變成 O。
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
if(m == 0) return;
int n = board[0].size();
if(n == 0) return;
for (int c=0; c<n; c++){
// Search 'O' in the first row
if (board[0][c] == 'O')
bfs(0, c, board);
// Search 'O' in the last row
if (board[m-1][c] == 'O')
bfs(m-1, c, board);
}
for (int r=0; r<m; r++) {
// Search 'O' in the first column
if (board[r][0] == 'O')
bfs(r, 0, board);
// Search 'O' in the last column
if (board[r][n-1] == 'O')
bfs(r, n-1, board);
}
for (int r=0; r<m; r++) {
for (int c = 0; c < n; c++) {
if (board[r][c] == 'O')
board[r][c] = 'X';
else if (board[r][c] == '#')
board[r][c] = 'O';
}
}
}
private:
void bfs(int i, int j, vector<vector<char>> &board) {
int m = board.size();
int n = board[0].size();
queue<pair<int, int> > q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> elem = q.front();
q.pop();
i = elem.first;
j = elem.second;
if (i >= 0 && i < m && j >=0 && j < n && board[i][j] == 'O') {
board[i][j] = '#';
q.push(make_pair(i - 1, j));
q.push(make_pair(i + 1, j));
q.push(make_pair(i, j - 1));
q.push(make_pair(i, j + 1));
}
}
}
};