Graph: Given a matrix, replace ‘o’ with ‘x’, if surrounded by ‘x’

Problem Statement:

You are given a matrix with either ‘x’ or ‘o’.

You need to replace all ‘o’ with ‘x’, if it is surrounded by x on all the sides.

Example:

Input: matrix =                [["X","X","X","X"],
 				 ["X","O","O","X"],
 				 ["X","X","O","X"],
 				 ["X","O","X","X"]]

Output:         [["X","X","X","X"],
		 ["X","X","X","X"],
		 ["X","X","X","X"],
		 ["X","O","X","X"]]

Solution Explanation:

Solution is very simple.

We check all the surrounding row and column if they are ‘o’, if they are ‘o’, we check for their neighbors are also ‘o’. Then replace them with ‘1’.

Now traverse the board and replace all the remaining ‘o’ to ‘x’ and all ‘1’ to ‘o’.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

void check(vector<vector<char>>& board, int i, int j) 
{
    if (board[i][j] == 'O') {
        board[i][j] = '1';
        if (i > 1) check(board, i - 1, j);
        if (j > 1) check(board, i, j - 1);
        if (i + 1 < board.size()) check(board, i + 1, j);
        if (j + 1 < board[0].size()) check(board, i, j + 1);
    }
}

void solution(vector<vector<char>>& board) 
{
    if (board.empty()) 
    	return;

    int row = board.size(); 
    int col = board[0].size();

    for (int i = 0; i < row; ++i) 
    {
        check(board, i, 0);             // first column
        check(board, i, col - 1);       // last column
    }

    for (int j = 1; j < col - 1; ++j) 
    {
        check(board, 0, j);             // first row
        check(board, row - 1, j);       // last row
    }

    for (int i = 0; i < row; ++i)
        for (int j = 0; j < col; ++j)
            if (board[i][j] == 'O') 
            	board[i][j] = 'X';
            else if (board[i][j] == '1') 
            	board[i][j] = 'O';
}

int main()
{
    vector<vector<char>> board = 
    {
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'}
    };

    solution(board);

    for (auto& row : board) {
        for (char c : row) {
            cout << c << " ";
        }
        cout << endl;
    }

    return 0;
}

Output

X X X X 
X X X X 
X X X X 
X O X X