# Replace ‘O’ With ‘X’

Posted: 31 Jul, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Given a 2D array grid G of 'O's and 'X's. The task is to replace all 'O' with 'X' contained in each island. Where, an island is a set of 'O's connected horizontally or vertically and surrounded by 'X' from all of it's boundaries. (Boundary means top, bottom, left and right)

##### Example:
``````{{X, X, O, X, X, X},
{X, X, O, X, O, X},
{X, X, X, O, O, X},
{X, O, X, X, X, X},
{O, X, O, O, X, X},
{X, X, X, X, O, X}}
``````

#### Note:

``````In the above example, elements at positions (0, 2) and (1,2) do not form an island as there is no 'X' surronding it from the top.
``````
##### Input Format:
``````The first line contains two integers 'N', 'M' representing the total number of rows and columns respectively.

Each of the next 'N' lines contains 'M' space-separated characters describing rows of the grid 'G' (each element of G is either 'O' or 'X').
``````
##### Output Format:
``````Print 'N' lines each contain 'M' space-separated characters describing the rows of replaced grid 'G'.
``````

#### Note:

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= 'N', 'M' <= 1000

Time Limit: 1 sec
`````` Approach 1
1. First, make a new 2D array of the same size as the input array. Let it be called arr. The input array will be called the matrix.
2. Then, we'll iterate through ‘matrix’ and check the value of the current element.
1. If it's equal to X, we'll assign arr as X at the same index.
2. Otherwise, we'll check whether there exists a path from the current element to any edge element (edge elements are the ones that are present in either the first row/column or the last row/column) such that all elements in the path are equal to O.
1. If such a path exists, we'll assign arr as O at the same index, otherwise, we'll assign arr as X
3. Finally, copy all elements of arr to the matrix.