Dada una array binaria mat[][] que consta de 1 y 0 de dimensión M * N , la tarea es encontrar el número de operaciones para convertir todos los 0 en 1. En cada operación, todos los 1 pueden convertir sus 0 adyacentes en 1.
Nota: Los elementos diagonales no se consideran elementos adyacentes de un número en la array.
Ejemplos:
Entrada: mat[][] = {{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 1, 0, 0}}
Salida: 2
Explicación: Todos los elementos adyacentes están en las direcciones izquierda/derecha/arriba/abajo.
La array antes de las operaciones será:
0 1 1 0 1
0 1 0 1 0
0 0 0 0 1
0 0 1 0 0
En el ejemplo anterior, las operaciones serían las siguientes:
Después de la operación 1, la array será:
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
Después de la Operación 2, la array será:
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
Nota: Los números en negrita indican los 0 modificados.
Acercarse:
- Atraviese toda la array y empuje las coordenadas de los elementos de la array con valor 1 en una cola .
- Guarde el tamaño de la cola en la variable x .
- Atraviesa la cola para x iteraciones.
- Para cada iteración, se encuentra la posición de un elemento con un valor 1. Convierta los valores en sus posiciones adyacentes a 1 (solo si los elementos adyacentes son 0) y luego envíe las coordenadas de los 1 recién convertidos a la cola.
- En cada una de las x iteraciones, elimine la cola del elemento frontal de la cola tan pronto como se realice el paso 4.
- Tan pronto como se atraviesen los x elementos de la cola, incremente la cuenta del número de operaciones a 1.
- Repita los pasos del 2 al 6 hasta que la cola esté vacía.
- Devuelve el recuento del número de operaciones después de que la cola esté vacía. Si la array tiene todos 1, no se realizará ninguna operación y el conteo será 0.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach.
#include <bits/stdc++.h>
using namespace std;
// function to check whether the
// adjacent neighbour is a valid
// index or not
bool check(int row, int col,
int r, int c) {
return (r >= 0 && r < row
&& c >= 0 && c < col);
}
// function to calculate the
// number of operations
int bfs(int row, int col,
int *grid) {
// direction matrix to find
// adjacent neighbours
int dir[4][2] = { { 1, 0 },
{ -1, 0 },
{ 0, 1 },
{ 0, -1 } };
// queue with pair to store
// the indices of elements
queue<pair<int, int> > q;
// scanning the matrix to push
// initial 1 elements
for (int i = 0; i < row; i++)
{
for (int j = 0;
j < col; j++) {
if (*((grid+i*col) + j))
q.push(make_pair(i, j));
}
}
// Step 2 to Step 6
int op = -1;
while (!q.empty()) {
int x = q.size();
for (int k = 0;
k < x; k++) {
pair<int, int> p =
q.front();
q.pop();
// adding the values of
// direction matrix to the
// current element to get
// 4 possible adjacent
// neighbours
for (int i = 0;
i < 4; i++) {
int r = p.first +
dir[i][0];
int c = p.second +
dir[i][1];
// checking the validity
// of the neighbour
if (*((grid+r*col) + c) == 0
&& check(row, col, r, c)) {
// pushing it to the queue
// and converting it to 1
q.push(make_pair(r, c));
*((grid+r*col) + c) = 1;
}
}
}
// increasing the operation by 1
// after the first pass
op++;
}
return op;
}
// Driver code
int main()
{
int row = 4, col = 5;
int grid[][col] =
{ { 0, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0 } };
cout << bfs(row, col,
(int *)grid);
}
Java
// Java code for the above approach.
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// function to check whether the
// adjacent neighbour is a valid
// index or not
static boolean check(int row, int col,
int r, int c) {
return (r >= 0 && r < row
&& c >= 0 && c < col);
}
// function to calculate the
// number of operations
static int bfs(int row, int col,
int [][]grid) {
// direction matrix to find
// adjacent neighbours
int dir[][] = { { 1, 0 },
{ -1, 0 },
{ 0, 1 },
{ 0, -1 } };
// queue with pair to store
// the indices of elements
Queue<pair > q = new LinkedList<GFG.pair>();
// scanning the matrix to push
// initial 1 elements
for (int i = 0; i < row; i++)
{
for (int j = 0;
j < col; j++) {
if (grid[i][j]!=0)
q.add(new pair(i, j));
}
}
// Step 2 to Step 6
int op = -1;
while (!q.isEmpty()) {
int x = q.size();
for (int k = 0;
k < x; k++) {
pair p =
q.peek();
q.remove();
// adding the values of
// direction matrix to the
// current element to get
// 4 possible adjacent
// neighbours
for (int i = 0;
i < 4; i++) {
int r = p.first +
dir[i][0];
int c = p.second +
dir[i][1];
// checking the validity
// of the neighbour
if (check(row, col, r, c) && grid[r] == 0) {
// pushing it to the queue
// and converting it to 1
q.add(new pair(r, c));
grid[r] = 1;
}
}
}
// increasing the operation by 1
// after the first pass
op++;
}
return op;
}
// Driver code
public static void main(String[] args)
{
int row = 4, col = 5;
int grid[][] =
{ { 0, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0 } };
System.out.print(bfs(row, col,
grid));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 code for the above approach. # function to check whether the # adjacent neighbour is a valid # index or not def check(row, col, r, c): return (r >= 0 and r < row and c >= 0 and c < col) # function to calculate the # number of operations def bfs(row, col, grid): # direction matrix to find # adjacent neighbours dir = [[1, 0], [-1, 0], [0, 1], [0, -1]] # queue with pair to store # the indices of elements q = [] # scanning the matrix to push # initial 1 elements for i in range(row): for j in range(col): if (grid[i][j]): q.insert(0, [i, j]) # Step 2 to Step 6 op = -1 while (len(q) != 0): x = len(q) for k in range(x): p = q[0] q.pop(0) # adding the values of # direction matrix to the # current element to get # 4 possible adjacent # neighbours for i in range(4): r = p[0] + dir[i][0] c = p[1] + dir[i][1] # checking the validity # of the neighbour if (check(row, col, r, c) and grid[r] == 0 ): # pushing it to the queue # and converting it to 1 q.insert(0, [r, c]) grid[r] = 1 # increasing the operation by 1 # after the first pass op += 1 return op #return 0 # Driver code if __name__ == "__main__": row = 4 col = 5 grid = [[0, 1, 1, 0, 1], [0, 1, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0]] print(bfs(row, col, grid)) # This code is contributed by ukasp.
C#
// C# code for the above approach.
using System;
using System.Collections.Generic;
public class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// function to check whether the
// adjacent neighbour is a valid
// index or not
static bool check(int row, int col,
int r, int c) {
return (r >= 0 && r < row
&& c >= 0 && c < col);
}
// function to calculate the
// number of operations
static int bfs(int row, int col,
int [,]grid) {
// direction matrix to find
// adjacent neighbours
int [,]dir = { { 1, 0 },
{ -1, 0 },
{ 0, 1 },
{ 0, -1 } };
// queue with pair to store
// the indices of elements
List<pair > q = new List<pair>();
// scanning the matrix to push
// initial 1 elements
for (int i = 0; i < row; i++)
{
for (int j = 0;
j < col; j++) {
if (grid[i,j]!=0)
q.Add(new pair(i, j));
}
}
// Step 2 to Step 6
int op = -1;
while (q.Count!=0) {
int x = q.Count;
for (int k = 0;
k < x; k++) {
pair p =
q[0];
q.RemoveAt(0);
// adding the values of
// direction matrix to the
// current element to get
// 4 possible adjacent
// neighbours
for (int i = 0;
i < 4; i++) {
int r = p.first +
dir[i,0];
int c = p.second +
dir[i,1];
// checking the validity
// of the neighbour
if (check(row, col, r, c) && grid[r,c] == 0) {
// pushing it to the queue
// and converting it to 1
q.Add(new pair(r, c));
grid[r,c] = 1;
}
}
}
// increasing the operation by 1
// after the first pass
op++;
}
return op;
}
// Driver code
public static void Main(String[] args)
{
int row = 4, col = 5;
int [,]grid =
{ { 0, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 1, 0, 0 } };
Console.Write(bfs(row, col,
grid));
}
}
// This code is contributed by shikhasingrajput
Producción:
2
Complejidad de tiempo: O(M * N)
Complejidad de espacio auxiliar: O(M * N)
Publicación traducida automáticamente
Artículo escrito por Shubham_12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA