Capturing Grid

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in company
Codenation

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
Hint

The connected component including ‘O’s at the boundary of the GRID will never be captured.

Approaches (1)
Flood Fill

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)

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

Void capture([char][] GRID)

  1. 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.
  2. 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’.
Time Complexity

O( N x M ), Where N and M are the numbers of rows and columns. 

 The DFS is performed for every ‘O’ at the boundary, which would go to NxM cells only 1 time.

Hence the time complexity is O( N x M ). 

Space Complexity

O( 1 ) 

Since we are only updating the original GRID without using any extra space.

Hence the space complexity is O( 1 ). 

Code Solution
(100% EXP penalty)
Capturing Grid
Full screen
Console