Last Updated: 26 Nov, 2020

Sum Of Zeroes

Easy

Asked in companies

Solve now

Problem statement

You are given a binary matrix (it contains only 0s and 1s) with dimensions ‘N * M’. You need to find and return the sum of coverages of all zeros of the given matrix.

Coverage for a particular 0 is defined as the total number of ‘1s’ around it (i.e., immediate left, immediate right, immediate up, and immediate bottom positions).

Input Format:

The first line of input contains an integer 'T' representing the number of the test cases. Then ‘T' test cases follow.

The first line of each test case contains two space-separated integers, 'N', 'M', the dimensions of the matrix. 

Next ‘N’ lines consist of ‘M’ space-separated integers denoting the matrix elements. Each element is either 0 or 1, as described in the problem statement.

Output Format:

For each test case, return the sum of coverage of all the 0s in the matrix.

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 <= N, M <= 10^3

Time limit: 1 second

Solve now

Approaches

01 Approach

For any 0 we just need to check its four adjacent sides and look for 1s in them. Therefore we could simply traverse the matrix, and if the current element is a 0, check how many of its adjacent neighbors are 1s and add this value to an integer variable ANS representing the result. In the end, return the value of ANS.

Steps:

Keep a variable ANS which will store our answer.
Traverse the matrix. Suppose i denotes the current row and j denotes the current column (1 <= i <= N, 1 <= j <= M).
- Let’s say the given matrix is MAT.
- If the current element is 0 then
  - If Mat[i-1][j](top neighbour) is 1, increment value of ANS by 1.
  - If Mat[i+1][j](bottom neighbour) is 1, increment value of ANS by 1.
  - If Mat[i][j-1](left neighbour) is 1, increment value of ANS by 1.
  - If Mat[i][j+1](right neighbour) is 1, increment value of ANS by 1.

Solve now