Replace ‘O’ With ‘X’

Posted: 31 Jul, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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}}

In the above example, there are 3 islands. Considering Zero based indexing of rows and columns, in the following islands described here, (x,y) represents the element in xth row and yth column.

Island 1: Formed by three elements at (1, 4), (2, 3), (2, 4) positions.

Island 2: Formed by a single element at (3, 1) position.

Island 3: Formed by two elements at (4, 2), (4, 3) positions.

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.
Try Problem