Dada una array de tamaño N que consta de 0 y 1 , la tarea es encontrar el tiempo mínimo requerido para llenar toda la array con 1 . Cada 1 en un instante en la array, puede convertir todos los 0 en 1 en sus ocho celdas adyacentes, es decir, un 1 presente en (i,j) puede convertir todos los 0 en 1 en las posiciones (i, j-1) , (i, j+1) , (i-1, j) , (i+1, j) , (i-1, j-1) , (i-1, j+1) , (i+1, j-1) ,(i+1, j+1) .
Ejemplos:
Entrada: N = 3, mtrx[][] = {{1,0,0},{0,0,1},{0,0,0}}
Salida: 2
Explicación:
Inicialmente, la array parece ser
1 , 0, 0
0, 0, 1
0, 0, 0
Después del primer instante de tiempo, la nueva array es
1, 1, 1
1, 1, 1
0, 1, 1
Después del segundo instante, el 0 restante se convierte en 1 .Entrada: N = 5,
mtrx[][] = {{0,0,0,0,0},
{1,0,0,0,0},
{0,0,0,0,0},
{ 0,0,1,0,0},
{0,0,0,1,0}}
Salida: 3
Enfoque:
Para resolver este problema, estamos utilizando el enfoque BFS . Atraviese la array y almacene los índices de la array con 1 inicialmente en una cola. Repita hasta que la cola se vacíe y convierta las celdas válidas adyacentes de todos los elementos de la cola en 1. La respuesta es el número de niveles de recorrido BFS que ha llevado a la conversión de al menos un 0 a 1.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ program to calculate the number of steps
// in fill all entire matrix with '1'
#include<bits/stdc++.h>
using namespace std;
// Function to return total number
// of steps required to fill
// entire matrix with '1'
int numberOfSteps(int n,vector<vector<int>> mtrx)
{
// Queue to store indices with 1
queue<pair<int,int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mtrx[i][j] == 1) {
q.push({i,j});
}
}
}
// Initialise step variable as zero
int step = 0 ;
// BFS approach
while (!q.empty())
{
int qsize = q.size();
// Visit all indices with 1 and
// fill its neighbouring cells by 1
while (qsize--)
{
pair<int,int> p = q.front();
q.pop();
int i = p.first;
int j = p.second;
// Convert the neighbour from '0' to '1'
if((j > 0) && mtrx[i][j-1] == 0)
{
mtrx[i][j-1] = 1;
q.push({i,j-1});
}
// Convert the neighbour from '0' to '1'
if((i < n-1) && mtrx[i+1][j] == 0)
{
mtrx[i+1][j] = 1;
q.push({i+1,j});
}
// Convert the neighbour from '0' to '1'
if((j < n-1) && mtrx[i][j+1] == 0)
{
mtrx[i][j+1] = 1;
q.push({i,j + 1});
}
// Convert the neighbour from '0' to '1'
if((i > 0) && mtrx[i-1][j] == 0)
{
mtrx[i-1][j] = 1;
q.push({i-1,j});
}
// Convert the neighbour from '0' to '1'
if((i > 0) && (j > 0) &&
mtrx[i-1][j-1] == 0)
{
mtrx[i-1][j-1] = 1;
q.push({i-1,j-1});
}
// Convert the neighbour from '0' to '1'
if((i > 0) && (j < (n-1)) &&
mtrx[i-1][j+1] == 0)
{
mtrx[i-1][j+1] = 1;
q.push({i-1,j+1});
}
// Convert the neighbour from '0' to '1'
if((i < (n-1)) && (j < (n-1)) &&
mtrx[i+1][j+1] == 0)
{
mtrx[i+1][j+1] = 1;
q.push({i+1,j + 1});
}
// Convert the neighbour from '0' to '1'
if((i < (n-1)) && (j > 0) &&
mtrx[i+1][j-1] == 0)
{
mtrx[i+1][j-1] = 1;
q.push({i+1,j-1});
}
}
//count steps
step++;
}
return step-1;
}
// Driver code
int main()
{
int n = 5 ; //dimension of matrix NXN
vector<vector<int>> mtrx = {{0,0,0,0,0},
{1,0,0,0,0},
{0,0,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0}};
// Print number of steps
cout << numberOfSteps(n, mtrx);
return 0;
}
Java
// Java program to calculate the
// number of steps in fill all
// entire matrix with '1'
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 return total number
// of steps required to fill
// entire matrix with '1'
static int numberOfSteps(int n, int[][] mtrx)
{
// Queue to store indices with 1
Queue<pair> q = new LinkedList<>();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if (mtrx[i][j] == 1)
{
q.add(new pair(i, j));
}
}
}
// Initialise step variable as zero
int step = 0;
// BFS approach
while (!q.isEmpty())
{
int qsize = q.size();
// Visit all indices with 1 and
// fill its neighbouring cells by 1
while (qsize-- > 0)
{
pair p = q.peek();
q.remove();
int i = p.first;
int j = p.second;
// Convert the neighbour from '0' to '1'
if ((j > 0) && mtrx[i][j - 1] == 0)
{
mtrx[i][j - 1] = 1;
q.add(new pair(i, j - 1));
}
// Convert the neighbour from '0' to '1'
if ((i < n - 1) && mtrx[i + 1][j] == 0)
{
mtrx[i + 1][j] = 1;
q.add(new pair(i + 1, j));
}
// Convert the neighbour from '0' to '1'
if ((j < n - 1) && mtrx[i][j + 1] == 0)
{
mtrx[i][j + 1] = 1;
q.add(new pair(i, j + 1));
}
// Convert the neighbour from '0' to '1'
if ((i > 0) && mtrx[i - 1][j] == 0)
{
mtrx[i - 1][j] = 1;
q.add(new pair(i - 1, j));
}
// Convert the neighbour from '0' to '1'
if ((i > 0) && (j > 0) &&
mtrx[i - 1][j - 1] == 0)
{
mtrx[i - 1][j - 1] = 1;
q.add(new pair(i - 1, j - 1));
}
// Convert the neighbour from '0' to '1'
if ((i > 0) && (j < (n - 1)) &&
mtrx[i - 1][j + 1] == 0)
{
mtrx[i - 1][j + 1] = 1;
q.add(new pair(i - 1, j + 1));
}
// Convert the neighbour from '0' to '1'
if ((i < (n - 1)) && (j < (n - 1)) &&
mtrx[i + 1][j + 1] == 0)
{
mtrx[i + 1][j + 1] = 1;
q.add(new pair(i + 1, j + 1));
}
// Convert the neighbour from '0' to '1'
if ((i < (n - 1)) && (j > 0) &&
mtrx[i + 1][j - 1] == 0)
{
mtrx[i + 1][j - 1] = 1;
q.add(new pair(i + 1, j - 1));
}
}
// Count steps
step++;
}
return step - 1;
}
// Driver code
public static void main(String[] args)
{
// Dimension of matrix NXN
int n = 5;
int [][]mtrx = { { 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 0, 1, 0 } };
// Print number of steps
System.out.print(numberOfSteps(n, mtrx));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python 3 program to calculate the number of steps # in fill all entire matrix with '1' # Function to return total number # of steps required to fill # entire matrix with '1' def numberOfSteps(n,mtrx): # Queue to store indices with 1 q = [] for i in range(n): for j in range(n): if (mtrx[i][j] == 1): q.append([i,j]) # Initialise step variable as zero step = 0 # BFS approach while (len(q)): qsize = len(q) # Visit all indices with 1 and # fill its neighbouring cells by 1 while(qsize): p = q[0] q.remove(q[0]) i = p[0] j = p[1] # Convert the neighbour from '0' to '1' if((j > 0) and mtrx[i][j - 1] == 0): mtrx[i][j - 1] = 1 q.append([i, j - 1]) # Convert the neighbour from '0' to '1' if((i < n-1) and mtrx[i + 1][j] == 0): mtrx[i + 1][j] = 1 q.append([i + 1, j]) # Convert the neighbour from '0' to '1' if((j < n-1) and mtrx[i][j + 1] == 0): mtrx[i][j + 1] = 1 q.append([i, j + 1]) # Convert the neighbour from '0' to '1' if((i > 0) and mtrx[i - 1][j] == 0): mtrx[i - 1][j] = 1 q.append([i - 1, j]) # Convert the neighbour from '0' to '1' if((i > 0) and (j > 0) and mtrx[i - 1][j - 1] == 0): mtrx[i - 1][j - 1] = 1 q.append([i - 1, j - 1]) # Convert the neighbour from '0' to '1' if((i > 0) and (j < (n-1)) and mtrx[i - 1][j + 1] == 0): mtrx[i - 1][j + 1] = 1 q.append([i - 1, j + 1]) # Convert the neighbour from '0' to '1' if((i < (n - 1)) and (j < (n - 1)) and mtrx[i + 1][j + 1] == 0): mtrx[i + 1][j + 1] = 1 q.append([i + 1, j + 1]) # Convert the neighbour from '0' to '1' if((i < (n - 1)) and (j > 0) and mtrx[i + 1][j - 1] == 0): mtrx[i + 1][j - 1] = 1 q.append([i + 1,j - 1]) qsize -= 1 #count steps step += 1 return step-1 # Driver code if __name__ == '__main__': #dimension of matrix NXN n = 5 mtrx = [[ 0, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ]] # Print number of steps print(numberOfSteps(n, mtrx)) # This code is contributed by Samarth
C#
// C# program to calculate the
// number of steps in fill all
// entire matrix with '1'
using System;
using System.Collections.Generic;
class GFG{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return total number
// of steps required to fill
// entire matrix with '1'
static int numberOfSteps(int n,
int[,] mtrx)
{
// Queue to store indices with 1
Queue<pair> q = new Queue<pair>();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if (mtrx[i, j] == 1)
{
q.Enqueue(new pair(i, j));
}
}
}
// Initialise step variable as zero
int step = 0;
// BFS approach
while (q.Count != 0)
{
int qsize = q.Count;
// Visit all indices
// with 1 and fill
// its neighbouring
// cells by 1
while (qsize-- > 0)
{
pair p = q.Peek();
q.Dequeue();
int i = p.first;
int j = p.second;
// Convert the neighbour
// from '0' to '1'
if ((j > 0) &&
mtrx[i, j - 1] == 0)
{
mtrx[i, j - 1] = 1;
q.Enqueue(new pair(i, j - 1));
}
// Convert the neighbour
// from '0' to '1'
if ((i < n - 1) &&
mtrx[i + 1, j] == 0)
{
mtrx[i + 1, j] = 1;
q.Enqueue(new pair(i + 1, j));
}
// Convert the neighbour
// from '0' to '1'
if ((j < n - 1) &&
mtrx[i, j + 1] == 0)
{
mtrx[i, j + 1] = 1;
q.Enqueue(new pair(i, j + 1));
}
// Convert the neighbour
// from '0' to '1'
if ((i > 0) &&
mtrx[i - 1, j] == 0)
{
mtrx[i - 1, j] = 1;
q.Enqueue(new pair(i - 1, j));
}
// Convert the neighbour
// from '0' to '1'
if ((i > 0) && (j > 0) &&
mtrx[i - 1, j - 1] == 0)
{
mtrx[i - 1, j - 1] = 1;
q.Enqueue(new pair(i - 1, j - 1));
}
// Convert the neighbour
// from '0' to '1'
if ((i > 0) && (j < (n - 1)) &&
mtrx[i - 1, j + 1] == 0)
{
mtrx[i - 1, j + 1] = 1;
q.Enqueue(new pair(i - 1, j + 1));
}
// Convert the neighbour
// from '0' to '1'
if ((i < (n - 1)) && (j < (n - 1)) &&
mtrx[i + 1, j + 1] == 0)
{
mtrx[i + 1, j + 1] = 1;
q.Enqueue(new pair(i + 1, j + 1));
}
// Convert the neighbour
// from '0' to '1'
if ((i < (n - 1)) && (j > 0) &&
mtrx[i + 1, j - 1] == 0)
{
mtrx[i + 1, j - 1] = 1;
q.Enqueue(new pair(i + 1, j - 1));
}
}
// Count steps
step++;
}
return step - 1;
}
// Driver code
public static void Main(String[] args)
{
// Dimension of matrix NXN
int n = 5;
int [,]mtrx = {{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 0}};
// Print number of steps
Console.Write(numberOfSteps(n, mtrx));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to calculate the number of steps
// in fill all entire matrix with '1'
// Function to return total number
// of steps required to fill
// entire matrix with '1'
function numberOfSteps(n,mtrx){
// Queue to store indices with 1
let q = []
for(let i = 0; i < n; i++)
{
for(let j = 0; j < n; j++)
{
if (mtrx[i][j] == 1)
q.push([i, j])
}
}
// Initialise step variable as zero
let step = 0
// BFS approach
while (q.length){
let qsize = q.length
// Visit all indices with 1 and
// fill its neighbouring cells by 1
while(qsize){
let p = q.shift()
let i = p[0]
let j = p[1]
// Convert the neighbour from '0' to '1'
if((j > 0) && mtrx[i][j - 1] == 0){
mtrx[i][j - 1] = 1
q.push([i, j - 1])
}
// Convert the neighbour from '0' to '1'
if((i < n-1) && mtrx[i + 1][j] == 0){
mtrx[i + 1][j] = 1
q.push([i + 1, j])
}
// Convert the neighbour from '0' to '1'
if((j < n-1) && mtrx[i][j + 1] == 0){
mtrx[i][j + 1] = 1
q.push([i, j + 1])
}
// Convert the neighbour from '0' to '1'
if((i > 0) && mtrx[i - 1][j] == 0){
mtrx[i - 1][j] = 1
q.push([i - 1, j])
}
// Convert the neighbour from '0' to '1'
if((i > 0) && (j > 0) &&
mtrx[i - 1][j - 1] == 0){
mtrx[i - 1][j - 1] = 1
q.push([i - 1, j - 1])
}
// Convert the neighbour from '0' to '1'
if((i > 0) && (j < (n-1)) &&
mtrx[i - 1][j + 1] == 0){
mtrx[i - 1][j + 1] = 1
q.push([i - 1, j + 1])
}
// Convert the neighbour from '0' to '1'
if((i < (n - 1)) && (j < (n - 1)) &&
mtrx[i + 1][j + 1] == 0){
mtrx[i + 1][j + 1] = 1
q.push([i + 1, j + 1])
}
// Convert the neighbour from '0' to '1'
if((i < (n - 1)) && (j > 0) &&
mtrx[i + 1][j - 1] == 0){
mtrx[i + 1][j - 1] = 1
q.push([i + 1,j - 1])
}
qsize -= 1
}
// count steps
step += 1
}
return step-1
}
// Driver code
// dimension of matrix NXN
let n = 5
let mtrx = [[ 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 1, 0 ]]
// Print number of steps
document.write(numberOfSteps(n, mtrx),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA