Capturing Grid

Moderate

0/80

Average time to solve is 20m

Contributed by

0 upvote

Asked in company

Problem statement

Given an ‘M’ x ‘N’ matrix ‘GRID’ containing ‘X’ and ‘O’, capture all the regions that are 4 directionally surrounded by ‘X’ and update the original 'GRID'.

A region is captured by flipping all ‘O’s to ‘X’s in that surrounding region.

Example:

Input: 
3 3
XXX
XOX
XXX

Output:     
XXX
XXX
XXX

Explanation:
The ‘O’ is surrounded by ‘X’s in all directions, so it is captured and flipped.

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 First line of each test case contains two integers, ‘N’ and ‘M’ denoting the number of rows and columns in the ‘GRID’.

The next ‘N’ lines of each test case contain ‘M’ characters, ‘O’ or ‘X’.

Output format :

Modify the original ‘GRID’ by flipping the captured ‘O’s.

Constraints :

1 <= T <= 10
1 <= N,M <= 200
Time Limit: 1 sec

Sample Input 1 :

2
3 3
XXX
XOX
XXX
3 4
XXXO
XXOX
XOXX

Sample Output 1 :

XXX
XXX
XXX
XXXO
XXXX
XOXX

Explanation Of Sample Input 1 :

Test 1:
The ‘O’ is surrounded by ‘X’s in all directions, so it is captured and flipped. 

Test 2:
The ‘O’ in the first row is only surrounded by 2 sides.
The ‘O’ in the second row is surrounded by all 4 sides, hence
flipped.
The ‘O’ in the third row is only surrounded by 3 sides.

Sample Input 2 :

2
3 3
XXX
XOX
XOX
3 4
OOXO
OXOX
OOXO

Sample Output 2 :

XXX
XOX
XOX
OOXO
OXXX
OOXO

Console