Wednesday, July 3, 2024
HomeData ModellingData Structure & AlgorithmCount all 0s which are blocked by 1s in binary matrix

Count all 0s which are blocked by 1s in binary matrix

Given Binary matrix. The task is to count all zeros which are surrounded by one (may not be an immediate neighbor). 

Note: here we are only taking four directions up, left, down, right. 

Examples: 

Input :  Int M[][] = {{ 0, 1, 1, 0},
                      { 1, 0, 0, 1},
                      { 0, 1, 0, 1},
                      { 1, 0, 1, 1}}
Output : 3 
Explanation : All zeros which are surrounded 
by 1 are (1, 1), (1, 2) and (2, 2)    

Idea is based on the DFS
First we remove all the zero value cells in the matrix which are reachable from the boundary of Matrix using DFS. Note that any cell which is reachable from a boundary 0 cell is not surrounded by ones. 

  Int M[][] =  {{  0, 1, 1,  0},
                { 1, 0, 0, 1},
                { 0, 1, 1, 1},
                { 1,  0, 1, 1}}
All zero cell which are reachable from boundary are in red color.

After that, we count all zeros which are left in binary matrix. 

Below is the implementation of above idea.

C++




// C++ program to count number of zeros
// surrounded by 1
#include <iostream>
using namespace std;
#define Row 4
#define Col 5
int r[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };
  
bool isSafe(int x, int y, int M[][Col])
{
    if (x >= 0 && x <= Row && y >= 0 &&
        y <= Col && M[x][y] == 0)
        return true;
    return false;
}
  
// DFS function to mark all reachable cells from
// (x, y)
void DFS(int x, int y, int M[][Col])
{
    // make it's visited
    M[x][y] = 1;
    for (int k = 0; k < 4; k++)
        if (isSafe(x + r[k], y + c[k], M))
            DFS(x + r[k], y + c[k], M);
}
  
// function return count of 0's which are surrounded by 1
int CountAllZero(int M[][Col])
{
    // first we remove all zeros which are not
    // surrounded by 1 that means we only remove 
    // those zeros which are reachable from
    // any boundary of given matrix.
    for (int i = 0; i < Col; i++)
        if (M[0][i] == 0)
            DFS(0, i, M);
    for (int i = 0; i < Col; i++)
        if (M[Row - 1][i] == 0)
            DFS(Row - 1, i, M);
    for (int i = 0; i < Row; i++)
        if (M[i][0] == 0)
            DFS(i, 0, M);
    for (int i = 0; i < Row; i++)
        if (M[i][Col - 1] == 0)
            DFS(i, Col - 1, M);
  
    // count all zeros which are surrounded by 1
    int result = 0;
    for (int i = 0; i < Row; i++)
        for (int j = 0; j < Col; j++)
            if (M[i][j] == 0)
                result++;
    return result;
}
  
// driver program to test above function
int main()
{
    int M[][Col] = { { 1, 1, 1, 0, 1 },
                     { 1, 0, 0, 1, 0 },
                     { 1, 0, 1, 0, 1 },
                     { 0, 1, 1, 1, 1 } };
    cout << CountAllZero(M) << endl;
    return 0;
}


Java




// Java program to count number of zeros
// surrounded by 1
class GFG {
  
    final static int Row = 4;
    final static int Col = 5;
    static int r[] = {0, 0, 1, -1};
    static int c[] = {1, -1, 0, 0};
  
    static boolean isSafe(int x, int y, int M[][]) {
        if (x >= 0 && x <Row && y >= 0
                && y < Col && M[x][y] == 0) {
            return true;
        }
        return false;
    }
  
// DFS function to mark all reachable cells from
// (x, y)
    static void DFS(int x, int y, int M[][]) {
        // make it's visited
        M[x][y] = 1;
        for (int k = 0; k < 4; k++) {
            if (isSafe(x + r[k], y + c[k], M)) {
                DFS(x + r[k], y + c[k], M);
            }
        }
    }
  
// function return count of 0's which are surrounded by 1
    static int CountAllZero(int M[][]) {
        // first we remove all zeros which are not
        // surrounded by 1 that means we only remove 
        // those zeros which are reachable from
        // any boundary of given matrix.
        for (int i = 0; i < Col; i++) {
            if (M[0][i] == 0) {
                DFS(0, i, M);
            }
        }
        for (int i = 0; i < Col; i++) {
            if (M[Row - 1][i] == 0) {
                DFS(Row - 1, i, M);
            }
        }
        for (int i = 0; i < Row; i++) {
            if (M[i][0] == 0) {
                DFS(i, 0, M);
            }
        }
        for (int i = 0; i < Row; i++) {
            if (M[i][Col - 1] == 0) {
                DFS(i, Col - 1, M);
            }
        }
  
        // count all zeros which are surrounded by 1
        int result = 0;
        for (int i = 0; i < Row; i++) {
            for (int j = 0; j < Col; j++) {
                if (M[i][j] == 0) {
                    result++;
                }
            }
        }
        return result;
    }
  
// driver program to test above function
    public static void main(String[] args) {
        int M[][] = {{1, 1, 1, 0, 1},
        {1, 0, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 1, 1, 1}};
        System.out.print(CountAllZero(M));
    }
}
// This code is contributed by Rajput-Ji


Python3




# Python3 program to count number of zeros 
# surrounded by 1 
Row = 4
Col = 5
r = [0, 0, 1, -1 ]
c = [1, -1, 0, 0 ]
  
def isSafe(x, y, M):
      
    if (x >= 0 and x < Row and y >= 0 and y < Col):
        if M[x][y] == 0:
            return True
      
    return False
  
# DFS function to mark all reachable cells from 
# (x, y) 
def DFS(x, y, M):
      
    # make it's visited 
    M[x][y] = 1
    for k in range(4):
        if (isSafe(x + r[k], y + c[k], M)):
            DFS(x + r[k], y + c[k], M) 
  
# function return count of 0's which are surrounded by 1 
def CountAllZero(M):
  
    # first we remove all zeros which are not 
    # surrounded by 1 that means we only remove 
    # those zeros which are reachable from 
    # any boundary of given matrix. 
    for i in range(Col):
        if (M[0][i] == 0):
            DFS(0, i, M) 
    for i in range(Col):
        if (M[Row - 1][i] == 0):
            DFS(Row - 1, i, M) 
    for i in range(Row): 
        if (M[i][0] == 0):
            DFS(i, 0, M) 
    for i in range(Row): 
        if (M[i][Col - 1] == 0):
            DFS(i, Col - 1, M) 
      
    # count all zeros which are surrounded by 1 
    result = 0
    for i in range(Row): 
        for j in range(Col):
            if (M[i][j] == 0):
                result += 1
      
    return result 
  
# Driver code 
M = [[1, 1, 1, 0, 1], [1, 0, 0, 1, 0 ], 
    [1, 0, 1, 0, 1] , [ 0, 1, 1, 1, 1 ]] 
print(CountAllZero(M))
  
# This code is contributed by shubhamsingh10


C#




      
// C# program to count number of zeros
// surrounded by 1
using System;
public class GFG {
   
    readonly static int Row = 4;
    readonly static int Col = 5;
    static int []r = {0, 0, 1, -1};
    static int []c = {1, -1, 0, 0};
   
    static bool isSafe(int x, int y, int [,]M) {
        if (x >= 0 && x <Row && y >= 0
                && y < Col && M[x,y] == 0) {
            return true;
        }
        return false;
    }
   
// DFS function to mark all reachable cells from
// (x, y)
    static void DFS(int x, int y, int [,]M) {
        // make it's visited
        M[x,y] = 1;
        for (int k = 0; k < 4; k++) {
            if (isSafe(x + r[k], y + c[k], M)) {
                DFS(x + r[k], y + c[k], M);
            }
        }
    }
   
// function return count of 0's which are surrounded by 1
    static int CountAllZero(int [,]M) {
        // first we remove all zeros which are not
        // surrounded by 1 that means we only remove 
        // those zeros which are reachable from
        // any boundary of given matrix.
        for (int i = 0; i < Col; i++) {
            if (M[0,i] == 0) {
                DFS(0, i, M);
            }
        }
        for (int i = 0; i < Col; i++) {
            if (M[Row - 1,i] == 0) {
                DFS(Row - 1, i, M);
            }
        }
        for (int i = 0; i < Row; i++) {
            if (M[i,0] == 0) {
                DFS(i, 0, M);
            }
        }
        for (int i = 0; i < Row; i++) {
            if (M[i,Col - 1] == 0) {
                DFS(i, Col - 1, M);
            }
        }
   
        // count all zeros which are surrounded by 1
        int result = 0;
        for (int i = 0; i < Row; i++) {
            for (int j = 0; j < Col; j++) {
                if (M[i,j] == 0) {
                    result++;
                }
            }
        }
        return result;
    }
   
// driver program to test above function
    public static void Main() {
        int [,]M = {{1, 1, 1, 0, 1},
        {1, 0, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 1, 1, 1}};
        Console.Write(CountAllZero(M));
    }
// This code is contributed by 29AjayKumar


Javascript




<script>
  
// Javascript program to count number of zeros
// surrounded by 1
var Row = 4;
var Col = 5;
var r = [ 0, 0, 1, -1 ];
var c = [ 1, -1, 0, 0 ];
  
function isSafe(x, y, M)
{
    if (x >= 0 && x < Row && y >= 0 &&
        y < Col && M[x][y] == 0)
        return true;
    return false;
}
  
// DFS function to mark all reachable cells from
// (x, y)
function DFS(x, y, M)
{
    // make it's visited
    M[x][y] = 1;
    for (var k = 0; k < 4; k++)
        if (isSafe(x + r[k], y + c[k], M))
            DFS(x + r[k], y + c[k], M);
}
  
// function return count of 0's which are surrounded by 1
function CountAllZero(M)
{
    // first we remove all zeros which are not
    // surrounded by 1 that means we only remove 
    // those zeros which are reachable from
    // any boundary of given matrix.
    for (var i = 0; i < Col; i++)
        if (M[0][i] == 0)
            DFS(0, i, M);
    for (var i = 0; i < Col; i++)
        if (M[Row - 1][i] == 0)
            DFS(Row - 1, i, M);
    for (var i = 0; i < Row; i++)
        if (M[i][0] == 0)
            DFS(i, 0, M);
    for (var i = 0; i < Row; i++)
        if (M[i][Col - 1] == 0)
            DFS(i, Col - 1, M);
  
    // count all zeros which are surrounded by 1
    var result = 0;
    for (var i = 0; i < Row; i++)
        for (var j = 0; j < Col; j++)
            if (M[i][j] == 0)
                result++;
    return result;
}
  
// driver program to test above function
var M = [ [ 1, 1, 1, 0, 1 ],
                 [ 1, 0, 0, 1, 0 ],
                 [ 1, 0, 1, 0, 1 ],
                 [ 0, 1, 1, 1, 1 ] ];
document.write( CountAllZero(M));
  
</script>


Output

4

Time Complexity: O(Row*Col)

Auxiliary Space: O(Row×Col)

This article is contributed by Nishant Singh. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks. 

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Nango Kalahttps://www.kala.co.za
Experienced Support Engineer with a demonstrated history of working in the information technology and services industry. Skilled in Microsoft Excel, Customer Service, Microsoft Word, Technical Support, and Microsoft Office. Strong information technology professional with a Microsoft Certificate Solutions Expert (Privet Cloud) focused in Information Technology from Broadband Collage Of Technology.
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments