Dada una array de array 2-D [][] de tamaño M*N y un número entero K. Para cada aparición de K en la array[][] , reemplace K y todos los elementos adyacentes distintos de cero a su izquierda , derecha , arriba y abajo con 0 . El programa debe repetir el proceso hasta que todos los valores de la array sean cero. La tarea es encontrar el número mínimo de pasos requeridos para convertir la array dada [][] a 0. Si es imposible, imprima -1.
Nota: Un paso se define como elegir un índice con valor K y cambiar su valor a 0 junto con sus celdas adyacentes hasta que todas las celdas se conviertan en 0 o el índice salga del rango.
Ejemplos:
Entrada: M = 5, N = 5,
array[5][5] = {{5, 6, 0, 5, 6},
{1, 8, 8, 0, 2},
{5, 5, 5, 0, 6},
{4, 5, 5, 5, 0},
{8, 8, 8, 8, 8}},
K = 6
Salida: 2
Explicación: la primera aparición de 6 se encuentra en matrix[0][ 1], por lo que todos los elementos adyacentes distintos de cero de izquierda, derecha, arriba y abajo se vuelven cero, es decir,
5 6 0 0
1 8 8 0 0 0
5 5 5 —> 0 0 0
4 5 5 5 0 0 0 0
8 8 8 8 8 0 0 0 0
Entonces, después de realizar el proceso para la primera aparición de 6, la array se convierte en
0 0 0 5 6
0 0 0 0 2
0 0 0 0 6
0 0 0 0 0
0 0 0 0 0
La segunda aparición de 6 se encuentra en matrix[0][4], por lo que todos los elementos adyacentes distintos de cero de izquierda, derecha, arriba y abajo se vuelven cero después de realizar el proceso para la segunda ocurrencia de 6, la array se convierte en
0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0
0 0 0 0
0 0 0 0
Ahora, todos los valores de celda en la array se vuelven cero. Por lo tanto, la salida es 2Entrada: M = 4, N = 5,
array[4][5] = {{5, 0, 0, 5, 6},
{1, 0, 8, 1, 0},
{0, 5, 0, 0, 6},
{4, 5, 0, 5, 2}},
K = 5
Salida: 4
Enfoque: la idea es atravesar la array en las cuatro direcciones izquierda, derecha, arriba y abajo , y al encontrar una celda con valor K, use la búsqueda en profundidad para cambiar el valor de todos los elementos adyacentes a 0. Siga los pasos a continuación . para resolver este problema:
- Inicializar la variable interations_count a 0
- Iterar sobre el rango [0, M) usando la fila variable y realizar las siguientes tareas:
- Iterar sobre el rango [0, N) usando la variable col y realizar las siguientes tareas:
- Si matrix[row][col] es igual a K, entonces realice DFS usando recursividad para cambiar todos los valores de los elementos posibles a 0 . También aumente el valor de iterations_count en 1.
- Iterar sobre el rango [0, N) usando la variable col y realizar las siguientes tareas:
- Después de realizar los pasos anteriores, verifique si el valor de alguna celda es distinto de cero. En caso afirmativo, imprima -1, de lo contrario, imprima el valor de iterations_count como respuesta.
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 implement DFS
void traverse(int M, int N, vector<vector<int> >& matrix,
int row, int col)
{
// Check the boundary conditions
if (row >= 0 && row < M && col >= 0 && col < N) {
if (matrix[row][col] == 0) {
return;
}
// Change that non-zero
// adjacent element to zero
matrix[row][col] = 0;
// Traverse the matrix in left
traverse(M, N, matrix, row, col - 1);
// Traverse the matrix in Right
traverse(M, N, matrix, row, col + 1);
// Traverse the matrix in Top
traverse(M, N, matrix, row - 1, col);
//// Traverse the matrix in Bottom
traverse(M, N, matrix, row + 1, col);
}
}
void findCount(int M, int N, vector<vector<int> >& matrix,
int K)
{
int iterations_count = 0;
// Traverse the matrix and find any element
// equals K, if any elements is found
// increment the interations_count variable
// and pass the element to the traverse function
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
if (K == matrix[row][col]) {
iterations_count++;
traverse(M, N, matrix, row, col);
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] != 0) {
iterations_count = -1;
}
}
}
// Print the iterations count
cout << iterations_count;
}
int main()
{
// Initialize the values of M and N
int M = 5, N = 5;
// Assigning the elements of 5*5 matrix
vector<vector<int> > matrix = { { 5, 6, 0, 5, 6 },
{ 1, 8, 8, 0, 2 },
{ 5, 5, 5, 0, 6 },
{ 4, 5, 5, 5, 0 },
{ 8, 8, 8, 8, 8 } };
// Assign K as 6
int K = 6;
findCount(M, N, matrix, K);
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java program for the above approach
public class GFG {
// Function to implement DFS
static void traverse(int M, int N,int matrix[][],int row, int col)
{
// Check the boundary conditions
if (row >= 0 && row < M
&& col >= 0 && col < N) {
if (matrix[row][col] == 0) {
return;
}
// Change that non-zero
// adjacent element to zero
matrix[row][col] = 0;
// Traverse the matrix in left
traverse(M, N, matrix, row, col - 1);
// Traverse the matrix in Right
traverse(M, N, matrix, row, col + 1);
// Traverse the matrix in Top
traverse(M, N, matrix, row - 1, col);
//// Traverse the matrix in Bottom
traverse(M, N, matrix, row + 1, col);
}
}
static void findCount(int M, int N, int matrix[][],int K)
{
int iterations_count = 0;
// Traverse the matrix and find any element
// equals K, if any elements is found
// increment the interations_count variable
// and pass the element to the traverse function
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
if (K == matrix[row][col]) {
iterations_count++;
traverse(M, N, matrix, row, col);
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] != 0) {
iterations_count = -1;
}
}
}
// Print the iterations count
System.out.print(iterations_count);
}
// Driver Code
public static void main(String []args)
{
// Initialize the values of M and N
int M = 5, N = 5;
// Assigning the elements of 5*5 matrix
int matrix[][] = {
{ 5, 6, 0, 5, 6 },
{ 1, 8, 8, 0, 2 },
{ 5, 5, 5, 0, 6 },
{ 4, 5, 5, 5, 0 },
{ 8, 8, 8, 8, 8 } };
// Assign K as 6
int K = 6;
findCount(M, N, matrix, K);
}
}
// This code is contributed by AnkThon
Python3
# python program for the above approach # Function to implement DFS def traverse(M, N, matrix, row, col): # Check the boundary conditions if (row >= 0 and row < M and col >= 0 and col < N): if (matrix[row][col] == 0): return # Change that non-zero # adjacent element to zero matrix[row][col] = 0 # Traverse the matrix in left traverse(M, N, matrix, row, col - 1) # Traverse the matrix in Right traverse(M, N, matrix, row, col + 1) # Traverse the matrix in Top traverse(M, N, matrix, row - 1, col) # Traverse the matrix in Bottom traverse(M, N, matrix, row + 1, col) def findCount(M, N, matrix, K): iterations_count = 0 # Traverse the matrix and find any element # equals K, if any elements is found # increment the interations_count variable # and pass the element to the traverse function for row in range(0, M): for col in range(0, N): if (K == matrix[row][col]): iterations_count += 1 traverse(M, N, matrix, row, col) for i in range(0, M): for j in range(0, N): if (matrix[i][j] != 0): iterations_count = -1 # Print the iterations count print(iterations_count) # Driver Code if __name__ == "__main__": # Initialize the values of M and N M = 5 N = 5 # Assigning the elements of 5*5 matrix matrix = [[5, 6, 0, 5, 6], [1, 8, 8, 0, 2], [5, 5, 5, 0, 6], [4, 5, 5, 5, 0], [8, 8, 8, 8, 8]] # Assign K as 6 K = 6 findCount(M, N, matrix, K) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
public class GFG {
// Function to implement DFS
static void traverse(int M, int N,int [,]matrix,int row, int col)
{
// Check the boundary conditions
if (row >= 0 && row < M
&& col >= 0 && col < N) {
if (matrix[row, col] == 0) {
return;
}
// Change that non-zero
// adjacent element to zero
matrix[row, col] = 0;
// Traverse the matrix in left
traverse(M, N, matrix, row, col - 1);
// Traverse the matrix in Right
traverse(M, N, matrix, row, col + 1);
// Traverse the matrix in Top
traverse(M, N, matrix, row - 1, col);
//// Traverse the matrix in Bottom
traverse(M, N, matrix, row + 1, col);
}
}
static void findCount(int M, int N, int [,]matrix,int K)
{
int iterations_count = 0;
// Traverse the matrix and find any element
// equals K, if any elements is found
// increment the interations_count variable
// and pass the element to the traverse function
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
if (K == matrix[row, col]) {
iterations_count++;
traverse(M, N, matrix, row, col);
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i,j] != 0) {
iterations_count = -1;
}
}
}
// Print the iterations count
Console.WriteLine(iterations_count);
}
// Driver Code
public static void Main(String []args)
{
// Initialize the values of M and N
int M = 5, N = 5;
// Assigning the elements of 5*5 matrix
int [,]matrix = {
{ 5, 6, 0, 5, 6 },
{ 1, 8, 8, 0, 2 },
{ 5, 5, 5, 0, 6 },
{ 4, 5, 5, 5, 0 },
{ 8, 8, 8, 8, 8 } };
// Assign K as 6
int K = 6;
findCount(M, N, matrix, K);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to implement DFS
function traverse( M, N, matrix,
row, col)
{
// Check the boundary conditions
if (row >= 0 && row < M
&& col >= 0 && col < N) {
if (matrix[row][col] == 0) {
return;
}
// Change that non-zero
// adjacent element to zero
matrix[row][col] = 0;
// Traverse the matrix in left
traverse(M, N, matrix, row, col - 1);
// Traverse the matrix in Right
traverse(M, N, matrix, row, col + 1);
// Traverse the matrix in Top
traverse(M, N, matrix, row - 1, col);
//// Traverse the matrix in Bottom
traverse(M, N, matrix, row + 1, col);
}
}
function findCount(M, N,
matrix,
K)
{
let iterations_count = 0;
// Traverse the matrix and find any element
// equals K, if any elements is found
// increment the interations_count variable
// and pass the element to the traverse function
for (let row = 0; row < M; row++) {
for (let col = 0; col < N; col++) {
if (K == matrix[row][col]) {
iterations_count++;
traverse(M, N, matrix, row, col);
}
}
}
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
if (matrix[i][j] != 0) {
iterations_count = -1;
}
}
}
// Print the iterations count
document.write(iterations_count);
}
// Driver Code
// Initialize the values of M and N
let M = 5, N = 5;
// Assigning the elements of 5*5 matrix
let matrix
= [[ 5, 6, 0, 5, 6 ],
[ 1, 8, 8, 0, 2 ],
[ 5, 5, 5, 0, 6 ],
[ 4, 5, 5, 5, 0 ],
[ 8, 8, 8, 8, 8]];
// Assign K as 6
let K = 6;
findCount(M, N, matrix, K);
// This code is contributed by rohitsingh07052.
</script>
2
Complejidad temporal: O(M*N)
Espacio auxiliar: O(1)