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 = 4Col = 5r = [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.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
