Last Updated: 14 Sep, 2022

Capturing Grid

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

The solution to the problem lies in marking all the connected components of ‘O’s which also touches the boundary of the GRID as they are not surrounded by ‘X’s from all 4 directions so they can not be captured.

This can be implemented by performing Depth First Search for every ‘O’ at the boundary of the GRID and marking them. Now we can reiterate through the GRID and change the unmarked ‘O’s to ‘X’s and remaining to ‘O’s .

The steps are as follows :

Void DFS ([char][] GRID , int x , int y)

Mark GRID[x][y].
For (‘nextx’,’nexty’) in all 4 directions
- If ‘nextx’ and ‘nexty’ are valid
  - Call DFS for nextx and nexty.

Void capture([char][] GRID)

For ‘row’ in range 0 to N-1.
- For ‘col’ in range 0 to M-1.
  - If GRID[row][col] is ‘O’ and row/col are at the boundary
    - Call DFS for row, col.
For ‘row’ in range 0 to N-1.
- For ‘col’ in range 0 to M-1.
  - If GRID[[row][col] is marked
    - Set GRID[row][col] to ‘O’.
  - else
    - Set GRID[row][col] to ‘X’.

Solve now