# C++, cont space, mark free O and replace those not marked - my easy to read code

1. Find all O on the edge of the grid
2. for each of the above, do BFS traversal (note, recursion will give for large tests) replacing 'O' with 'o' - marking free 'O' cells
3. go over the whole grid and replace O=>X and o=>O

The code:

``````class Solution {
int _rows;
int _cols;

public:
void solve(vector<vector<char>> &board) {
if(board.size()<3 || board[0].size()<3) return;

_rows = board.size();
_cols = board[0].size();

for(int i=0; i<_rows;i++)
{
markFree(board,i,0);
markFree(board,i,_cols-1);
}
for(int j=1;j<_cols-1;j++)
{
markFree(board,0,j);
markFree(board,_rows-1,j);
}

for(int i=0; i<_rows;i++)
for(int j=0;j<_cols;j++)
{
if(board[i][j] == 'O') board[i][j] = 'X';
else if(board[i][j] == 'o') board[i][j] = 'O';
}
}

void markFree(vector<vector<char>> &board, int I, int J)
{
stack<pair<int,int>> items;

items.push(make_pair(I,J));

while(!items.empty())
{
pair<int,int> p = items.top();
items.pop();
int i = p.first;
int j = p.second;

if(board[i][j] == 'X' || board[i][j]=='o') continue;

if(board[i][j] == 'O') {
board[i][j] = 'o';
}

if(i < _rows-1) items.push(make_pair(i+1,j));
if(j < _cols-1) items.push(make_pair(i, j+1));
if(i>0) items.push(make_pair(i-1,j));
if(j>0) items.push(make_pair(i, j-1));
}
}
};``````

• cool, I use another hash table to record whether the position has been visited or not, your method are very efficiency

• nothing wrong with the code, but it is dfs not bfs

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