Input: 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
We can solve this problem in 2 ways:
- BFS
- DFS
In this tutorial we solve it by using DFS.
The solution here is very simple. First we check if any of the edges of row and column is ‘o’ and also check if their neighbour is also ‘o’ then replace them with the character “1”.
Then we convert all the remaining ‘o’ to ‘x’ and replace ‘1’ with ‘o’. We get our solution.
The steps can be pictorially shown as below:
X X X X X X X X X X X X X O O X ---> X O O X -then-> X X X X X X O X X X O X X X X X X O X X X 1 X X X O X X
Solution in C++
#include<iostream> #include<vector> using namespace std; //helper function void check(vector<vector<char>>& board, int i, int j) { if (board[i][j] == 'O') { // if the value is 'O' then replace it with '1' board[i][j] = '1'; // check if its neighbors is also 'O' by recursively calling this function 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 solve_using_dfs(vector<vector<char>>& board) { if (board.empty()) return; int row = board.size(); int col = board[0].size(); // check for column for (int i = 0; i < row; ++i) { check(board, i, 0); // first column check(board, i, col - 1); // last column } // check for rows for (int j = 1; j < col - 1; ++j) { check(board, 0, j); // first row check(board, row - 1, j); // last row } // Now replace 'O' with 'X' and '1' with 'O' 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'} }; solve_using_dfs(board); cout<<"The solution is "<<endl; for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { cout<< board[i][j]<<" "; } cout<<endl; } return 0; }
Output:
The solution is X X X X X X X X X X X X X O X X