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;
    
    // Check all adjacent nodes
    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[0].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][0] == 'O' and !visited[i][0])
        {
            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[0][i] == 'O' and !visited[0][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';
            }
        }
    }
}