New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Capturing Grid

Contributed by

imObscure

Medium

0/80

Avg time to solve 20 mins

Success Rate 70 %

0 upvotes

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, Constraints, 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

Auto

Console