Cuente todos los 0 que están bloqueados por 1 en la array binaria

Array binaria dada. La tarea es contar todos los ceros que están rodeados por uno (puede que no sea un vecino inmediato). 

Nota: aquí solo estamos tomando cuatro direcciones arriba, izquierda, abajo, derecha. 

Ejemplos: 

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)    

La idea se basa en el DFS . 
Primero eliminamos todas las celdas de valor cero en la array que son accesibles desde el límite de Matrix usando DFS. Tenga en cuenta que cualquier celda a la que se pueda acceder desde una celda de límite 0 no está rodeada de unos. 

  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 read color.

Después de eso, contamos todos los ceros que quedan en la array binaria. 

A continuación se muestra la implementación de la idea anterior.

// 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 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 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# 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

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

4

Complejidad de tiempo: O (fila * columna)

Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.