# C++ Bredth-first-search solution

• ``````class Solution {
public:
void solve(vector<vector<char> >& board) {
if (board.size() == 0) return;
int m = board.size();
int n = board[0].size();
vector<vector<bool> > visited(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && visited[i][j] == false && insideTheCircle(i, j, m, n)) {
vector<pair<int, int> > orders;
if (! bfs(i, j, m, n, board, orders, visited) )
continue;
for (auto p : orders) {
board[p.first][p.second] = 'X';
}
}
}
}
}

bool insideTheCircle(int i, int j, int m, int n) {
return (i > 0) && (i < m-1) && (j > 0) && (j < n-1);
}

bool bfs(int i, int j, int m, int n, vector<vector<char> >& board, vector<pair<int, int> >& orders, vector<vector<bool> >& visited) {
queue<pair<int, int> > q;
q.push(make_pair(i, j));
visited[i][j] = true;
int hasBoundaryO = false;
while (!q.empty()) {
auto p = q.front(); q.pop();
i = p.first;
j = p.second;
orders.push_back(p);
//access right
if (j + 1 < n && visited[i][j+1] == false && board[i][j+1] == 'O') {
visited[i][j+1] = true;
if (insideTheCircle(i, j+1, m, n))
q.push(make_pair(i, j+1));
else // I made a mistake here: if there is boundary zero, do not directly return, still iterate all Oes
// but keep a flag to judge whether the area covered using BFS is valid
hasBoundaryO = true;
}
//access down
if (i + 1 < m && visited[i+1][j] == false && board[i+1][j] == 'O') {
visited[i+1][j] = true;
if (insideTheCircle(i+1, j, m, n))
q.push(make_pair(i+1, j));
else
hasBoundaryO = true;
}
//access up
if (i - 1 >= 0 && visited[i-1][j] == false && board[i-1][j] == 'O') {
visited[i-1][j] = true;
if (insideTheCircle(i-1, j, m, n))
q.push(make_pair(i-1, j));
else
hasBoundaryO = true;
}
//access left
if (j - 1 >= 0 && visited[i][j-1] == false && board[i][j-1] == 'O') {
visited[i][j-1] = true;
if (insideTheCircle(i, j-1, m, n))
q.push(make_pair(i, j-1));
else
hasBoundaryO = true;
}
}
return !hasBoundaryO;
}
};``````

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