Problem

Submissions

Hints & solutions

Discuss

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

Hint 1

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

Approaches (1)

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

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’.

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

(100% EXP penalty)

Capturing Grid

Divyanshu Kumar

Interview problems

C++ / CPP CODE || USE DFS

void dfs(int row , int col ,vector<vector<int>>& vis,vector<vector<char>> &mat,vector<int> delRow , vector<int> delCol){

vis[row][col]=1;

int n = mat.size();

int m = mat[0].size();

for(int i=0;i<4;i++){

int newRow = row + delRow[i];

int newCol = col + delCol[i];

if(newRow >=0 && newRow <n && newCol >=0 && newCol <m &&

!vis[newRow][newCol] && mat[newRow][newCol]=='O'){

dfs(newRow , newCol , vis , mat , delRow , delCol);

}

void capture(vector<vector<char>> &mat) {

// Write your code from here.

int n=mat.size();

int m=mat[0].size();

vector<int>delRow={-1,0,+1,0};

vector<int>delCol={0,+1,0,-1};

vector<vector<int>>vis(n,vector<int>(m,0));

// traverse for row.

for(int j=0;j<m;j++){

//first row

if(!vis[0][j] && mat[0][j]=='O'){

dfs(0,j,vis , mat ,delRow , delCol);

}

//last row

if(!vis[n-1][j] && mat[n-1][j]=='O')

dfs(n-1,j,vis,mat,delRow,delCol);

}

//traversing first col and last col

for(int i=0;i<n;i++){

//first col

if(!vis[i][0] && mat[i][0]=='O')

dfs(i,0,vis,mat,delRow,delCol);

//last col

if(!vis[i][m-1] && mat[i][m-1]=='O')

dfs(i,m-1,vis,mat,delRow,delCol);

}

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

// if(!vis[i][j] && mat[i][j]=='O')

// mat[i][j]='X';

if(vis[i][j]==0){

mat[i][j]='X';

}

else{

mat[i][j]='O';

}

datastructures

algorithms

33 views

0 replies

0 upvotes

Console