 # C++ O[N*M] Neat solution with approach and comments, using DFS, suggestions welcome :)

#1
``````int n, m;
void DFS(vector<vector<char>> &A, int i, int j, vector<vector<bool>> &visited)
{
// Mark current node as visited
visited[i][j] = true;

if(i > 0 and !visited[i - 1][j] and A[i - 1][j] == 'O')
{
DFS(A, i - 1, j, visited);
}

if(i + 1 < n and !visited[i + 1][j] and A[i + 1][j] == 'O')
{
DFS(A, i + 1, j, visited);
}

if(j > 0 and !visited[i][j - 1] and A[i][j - 1] == 'O')
{
DFS(A, i, j - 1, visited);
}

if(j + 1 < m and !visited[i][j + 1] and A[i][j + 1] == 'O')
{
DFS(A, i, j + 1, visited);
}
}

void Solution::solve(vector<vector<char>> &A)
{
/* Approach
1. Check all the boundaries of the given matrix.
2. If any 'O' found on boundary, run DFS starting from this 'O' and mark
all chaining Os as visited.
3. All non - visited Os will be converted to X, in one final matrix sweep.
*/

n = A.size();
m = A.size();
vector<vector<bool>> visited(n, vector<bool>(m, false));

// First check first row and last row, for any 'O'
for(int i = 0; i < n; i++)
{
//If any 'O' found, find all adjacent 'O's and mark them visited
if(A[i] == 'O' and !visited[i])
{
DFS(A, i, 0, visited);
}
if(A[i][m - 1] == 'O' and !visited[i][m - 1])
{
DFS(A, i, m - 1, visited);
}
}

// Next check first column and last column, for any 'O'
for(int i = 0; i < m; i++)
{
// Check boundaries. If any O found, find any adjacent O's to it
if(A[i] == 'O' and !visited[i])
{
DFS(A, 0, i, visited);
}
if(A[n - 1][i] == 'O' and !visited[n - 1][i])
{
DFS(A, n - 1, i, visited);
}
}

// Now a final sweep to simply convert all non visited 'O' to 'X'
// Note that boundary O's will never be converted, so, can reduce the loop
for(int i = 1; i < n - 1; i++)
{
for(int j = 1; j < m - 1; j++)
{
if(A[i][j] == 'O' and !visited[i][j])
{
A[i][j] = 'X';
}
}
}
}

``````