Topics

# Capturing Grid

Moderate
0/80
Average time to solve is 20m
Contributed by
0 upvote

## 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 )
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