Problem

Submissions

Hints & solutions

Discuss

Capture region

Moderate

0/80

Average time to solve is 10m

Contributed by

13 upvotes

Asked in companies

Problem statement

You are given a matrix having ‘N’ rows and ‘M’ columns. Each cell of the matrix is either ‘X’ or ‘O’. You need to flip all those regions of ‘O’ which are surrounded by ‘X’ i.e. you need to change all ‘O’s which are present in the region to ‘X’.

Note

1. Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the matrix is not flipped to 'X'. 
2. Any ‘O’ or group of connected ‘O’ are said to be surrounded by ‘X’ when all cells touching the boundary of the group of ‘O’ must contain ‘X’.

For example

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The next 2 * T lines describe the ‘T’ test cases.

The first line of each test case contains two space-separated positive integers ‘N’ and ‘M’ denoting the number of the rows and columns in a matrix respectively. 

In the next ‘N’ lines of each test case, the ith line contains a string of length ‘M’ containing either ‘X’ or ‘O’.

Output Format:

For each test case, print N lines each line containing M characters denoting the matrix element at position MATRIX[i][j] where i and j are the indices of the 2 - D array.

The output of each test case will begin from a new line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10 ^ 4  
1 <= M <= 10 ^ 4
1 <= N * M <= 10 ^ 4 

Where ‘T’ is the number of test cases, ‘N’ is the number of rows, ‘M’ is the number of columns.

Time Limit: 1 sec

Sample Input 1:

2
2 2
XO
OX
5 3
XXX
XOX
XXX
XOX
OOO

Sample Output 1:

XO
OX
XXX
XXX
XXX
XOX
OOO

Explanation for sample input 1:

Test case 1:
The Os present at [0,1] and [1,0] both lies on boundaries hence they remain as it is.

Test case 2:
The Os present at [4,0], [4,1], and [4,2] lies on boundaries hence they remain as it is.
The O present at [3,1] is connected to O present at boundaries so it will also remain the same.
The O present at [1,1] is not connected to any O which lies on the boundary so it will be considered as a captured region. Hence they will be flipped to X.

Sample Input 2:

2
3 3
OOO
OXO
OOO
3 3
XXX
XOX
XXX

Sample Output 2:

OOO
OXO
OOO
XXX
XXX
XXX

Hint 1

Hint 2

Perform a traversal from each cell, wonder which traversal can be used think it in form of recursive traversal.

Approaches (2)

Approach 1

Approach 2

Brute force, DFS

We will run two nested loops to traverse each cell of the matrix.
For each cell containing ‘O’, we perform DFS in which we go to all adjacent neighbors containing ‘O’.
The DFS function will tell us whether from this cell we can reach the boundary or not. If there is a way to reach the boundary from any of the neighbor cells of the current cell then this current cell can also reach the boundary through the neighbor cell. Hence this cell can’t be part of a region.
If there is no way to reach the boundary then the current cell will be changed to ‘X’.

Time Complexity

O(N ^ 2 * M ^ 2), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.

We using two nested loops for traversing each element in a matrix that will take O(N * M) time.

For each cell, we perform a DFS which can traverse on all the elements in the worst case so it will take O(N * M) time.

Total time complexity O((N * M) ^ 2)

Space Complexity

O(N * M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.

In the worst case, the DFS recursive function stack can have ‘N * M’ entries.

(100% EXP penalty)

Capture region

Console