Last Updated: 2 Nov, 2021

Count Good Islands

Moderate

Asked in company

Solve now

Problem statement

You are given two matrices, ‘MATRIX1’ and ‘MATRIX2’ of size ‘M’ x ‘N’ having 0s and 1s only, where ‘0’ in the matrix represents water, and ‘1’ in the matrix represents the land. An island is a group of 1s connected horizontally and vertically. An island in ‘MATRIX2’ is considered to be good if there is an island in ‘MATRIX1’ that contains all the cells that make up this island in ‘MATRIX2’. You have the find the count of good islands.

For example :

Let ‘MATRIX1’ be : 
1 1
0 0

Let ‘MATRIX2’ be: 
1 1
0 0

All the 1s present in ‘MATRIX2’ can be considered a good island. There is 1 good island present.

Input Format :

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M’ and ‘N’, representing the size of the matrices.

The next ‘M’  lines of each test case contain ‘N’ space-separated integers, representing the cells of ‘MATRIX1’.

The next ‘M’  lines of each test case contain ‘N’ space-separated integers, representing the cells of ‘MATRIX2’.

Output Format :

For each test case, print the number of good islands.

Print output of each test case in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= M, N <= 10^3
0 <= MATRIX1[i][j], MATRIX2[i][j] <= 1

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to find the ‘1’ present in ‘MATRIX2’ which is not visited yet and then recursively traverse all the cells present on that island while checking for the ‘1s’ present in the ‘MATRIX1’ at the same position or not. If all the cells of an island in ‘MATRIX2’ are present in the ‘MATRIX1’, we count it as a good island. We also change the value of visited cells to ‘-1’ so we don’t traverse them again.

Here is the algorithm :

Create a variable (say, ‘ANS’) that will store the number of good islands and initialize it with 0.
Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse all the rows.
- Run a loop from 0 to ‘N’ (say, iterator ‘j’) to traverse all the columns
  - Check if ‘MATRIX2[i][j]’ is equal to 1.
    - Create a variable (say, ‘GOOD’) to check whether the island is good or not and initialize it with ‘true’.
    - Call the DFS function on the current position to check for the cells on the island.
    - Check if ‘GOOD’ is ‘true’, update ‘ANS’ by 1.
Return ‘ANS’.

DFS(‘M’, ‘N’, ‘MATRIX1’, ‘MATRIX2’, ‘i’, ‘j’, ‘GOOD’) (where ‘M’ and ‘N’ are the size of the matrices, ‘MATRIX1’ and ‘MATRIX2’ are the given matrices, ‘i’ and ‘j’ are starting position, and ‘GOOD’ is for checking the validity of good island).

Base case:
- Check if ‘i’ is smaller than 0 or greater than equal to ‘M’ or ‘j’ is smaller than 0 or greater than equal to ‘N’ or ‘MATRIX2[i][j]’ is not equal to 1.
  - Return.
Mark ‘MATRIX2[i][j]’ as visited by updating the cell’s value to ‘-1’.
Check if value of ‘MATRIX1[i][j]’ is equal to 0.
- Update ‘GOOD’ to ‘false’.
Traverse in all 4 directions of the matrix by updating ‘i’ and ‘j’.

Solve now

02 Approach

The basic idea is to find the 1s in the ‘MATRIX2’ which are not visited yet and then check whether the same position consists of 1s or not in the ‘MATRIX1’. We use bfs traversal to find the number of good islands. Initially, we insert 1s present in the ‘MATRIX2’ in a queue and then keep on traveling in 4 different directions while checking for the 1s in the ‘MATRIX1’. If all the cells of an island in ‘MATRIX2’ are present in the ‘MATRIX1’, we count it as a good island. We also change the value of visited cells to ‘-1’ so we don’t traverse them again.

Here is the algorithm :

Create a variable (say, ‘ANS’) that will store the number of good islands and initialize it with 0.
Create an array (say, ‘DIR’) that will store the directions to move.
Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse all the rows.
- Run a loop from 0 to ‘N’ (say, iterator ‘j’) to traverse all the columns
  - Check if ‘MATRIX2[i][j]’ and ‘MATRIX1[i][j]’ is equal to 1.
    - Create a variable (say, ‘GOOD’) to check whether the island is good or not and initialize it with ‘true’.
    - Create a queue (say, ‘Q’) to store the ‘1s’ and initially insert ‘i’ and ‘j’ in the queue.
    - Mark ‘MATRIX2[i][j]’ as visited by updating the cell’s value to ‘-1’.
    - Run a loop till ‘Q’ is not empty.
      - Traverse in all 4 directions of the matrix by updating ‘i’ and ‘j’. (let indices be ‘X’ and ‘Y’).
      - Check if ‘X’ is smaller than 0 or greater than equal to ‘M’ or ‘Y’ is smaller than 0 or greater than equal to ‘N’, continue.
      - Check if the value of ‘MATRIX2[X][Y]‘ is equal to 1 and MATRIX1[X][Y]’ is equal to 0, update ‘GOOD’ to ‘false’.
      - Check if the value of ‘MATRIX2[X][Y]‘ is equal to 1 and MATRIX1[X][Y]’ is equal to 1, mark ‘X’ and ‘Y’ as visited and push ‘X’ and ‘Y’ in ‘Q’.
    - Check if ‘GOOD’ is ‘true’, update ‘ANS’ by 1.
Return ‘ANS’.

Solve now