# A solution by bfs

• ``````class Solution {
public:
void solve(vector<vector<char>> &board) {
if (board.empty()) return;
const int m = board.size();
const int n = board[0].size();
for (int i = 0; i < n; i++) {
bfs(board, 0, i);
bfs(board, m - 1, i);
}
for (int j = 1; j < m-1; j++) {
bfs(board, j, 0);
bfs(board, j, n - 1);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O')
board[i][j] = 'X';
else if (board[i][j] == '+')
board[i][j] = 'O';
}
}
}
private:
typedef struct { int x; int y; } state;
void bfs(vector<vector<char>> &board, int i, int j) {
queue<state> myq;
const int m = board.size();
const int n = board[0].size();
state start = { i,j };
if (is_valid(start, board)) {
board[i][j] = '+';
myq.push(start);
}
while (!myq.empty()) {
auto cur = myq.front();
myq.pop();
auto new_states = state_extend(cur, board);
for (auto s : new_states) myq.push(s);
}
}
bool is_valid(state &s, vector<vector<char>> &board) {
const int x = s.x;
const int y = s.y;
const int m = board.size();
const int n = board[0].size();
if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O')
return false;
return true;
}
vector<state> state_extend(const state &s, vector<vector<char>> &board) {
vector<state> result;
const int x = s.x;
const int y = s.y;
state new_states[4] = { { x - 1,y },{ x + 1,y },
{ x,y - 1 },{ x,y + 1 } };
for (int i = 0; i < 4; ++i) {
if (is_valid(new_states[i], board)){
board[new_states[i].x][new_states[i].y] = '+';
result.push_back(new_states[i]);
}
}
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.