Dada una array binaria de N x M , que contiene al menos un valor de 1. La tarea es encontrar la distancia del 1 más cercano en la array para cada celda. La distancia se calcula como |i 1 – i 2 | + | j 1 – j 2 | , donde i 1 , j 1 son el número de fila y el número de columna de la celda actual e i 2 , j 2 son el número de fila y el número de columna de la celda más cercana que tiene el valor 1.
Ejemplos:
Input : N = 3, M = 4
mat[][] = { 0, 0, 0, 1,
0, 0, 1, 1,
0, 1, 1, 0 }
Output : 3 2 1 0
2 1 0 0
1 0 0 1
Explanation:
For cell at (0, 0), nearest 1 is at (0, 3),
so distance = (0 - 0) + (3 - 0) = 3.
Similarly, all the distance can be calculated.
Input : N = 3, M = 3
mat[][] = { 1, 0, 0,
0, 0, 1,
0, 1, 1 }
Output :
0 1 1
1 1 0
1 0 0
Explanation:
For cell at (0, 1), nearest 1 is at (0, 0), so distance
is 1. Similarly, all the distance can be calculated.
Método 1: este método utiliza un enfoque simple de fuerza bruta para llegar a la solución.
- Enfoque: La idea es recorrer la array para cada celda y encontrar la distancia mínima. Para encontrar la distancia mínima, atravesar la array y encontrar la celda que contiene 1 y calcula la distancia entre dos celdas y almacena la distancia mínima.
- Algoritmo:
- Atraviesa la array de principio a fin (usando dos bucles anidados)
- Para cada elemento, busque el elemento más cercano que contenga 1. Para encontrar el elemento más cercano, recorra la array y encuentre la distancia mínima.
- Rellene la distancia mínima en la array.
Implementación:
C++
// C++ program to find distance of nearest
// cell having 1 in a binary matrix.
#include<bits/stdc++.h>
#define N 3
#define M 4
using namespace std;
// Print the distance of nearest cell
// having 1 for each cell.
void printDistance(int mat[N][M])
{
int ans[N][M];
// Initialize the answer matrix with INT_MAX.
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
ans[i][j] = INT_MAX;
// For each cell
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
// Traversing the whole matrix
// to find the minimum distance.
for (int k = 0; k < N; k++)
for (int l = 0; l < M; l++)
{
// If cell contain 1, check
// for minimum distance.
if (mat[k][l] == 1)
ans[i][j] = min(ans[i][j],
abs(i-k) + abs(j-l));
}
}
// Printing the answer.
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
// Driven Program
int main()
{
int mat[N][M] =
{
0, 0, 0, 1,
0, 0, 1, 1,
0, 1, 1, 0
};
printDistance(mat);
return 0;
}
Java
// Java program to find distance of nearest
// cell having 1 in a binary matrix.
import java.io.*;
class GFG {
static int N = 3;
static int M = 4;
// Print the distance of nearest cell
// having 1 for each cell.
static void printDistance(int mat[][])
{
int ans[][] = new int[N][M];
// Initialize the answer matrix with INT_MAX.
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
ans[i][j] = Integer.MAX_VALUE;
// For each cell
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
// Traversing the whole matrix
// to find the minimum distance.
for (int k = 0; k < N; k++)
for (int l = 0; l < M; l++)
{
// If cell contain 1, check
// for minimum distance.
if (mat[k][l] == 1)
ans[i][j] =
Math.min(ans[i][j],
Math.abs(i-k)
+ Math.abs(j-l));
}
}
// Printing the answer.
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
System.out.print( ans[i][j] + " ");
System.out.println();
}
}
// Driven Program
public static void main (String[] args)
{
int mat[][] = { {0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0} };
printDistance(mat);
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to find distance of # nearest cell having 1 in a binary matrix. # Print distance of nearest cell # having 1 for each cell. def printDistance(mat): global N, M ans = [[None] * M for i in range(N)] # Initialize the answer matrix # with INT_MAX. for i in range(N): for j in range(M): ans[i][j] = 999999999999 # For each cell for i in range(N): for j in range(M): # Traversing the whole matrix # to find the minimum distance. for k in range(N): for l in range(M): # If cell contain 1, check # for minimum distance. if (mat[k][l] == 1): ans[i][j] = min(ans[i][j], abs(i - k) + abs(j - l)) # Printing the answer. for i in range(N): for j in range(M): print(ans[i][j], end = " ") print() # Driver Code N = 3 M = 4 mat = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 0]] printDistance(mat) # This code is contributed by PranchalK
C#
// C# program to find the distance of nearest
// cell having 1 in a binary matrix.
using System;
class GFG {
static int N = 3;
static int M = 4;
// Print the distance of nearest cell
// having 1 for each cell.
static void printDistance(int [,]mat)
{
int [,]ans = new int[N,M];
// Initialise the answer matrix with int.MaxValue.
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
ans[i,j] = int.MaxValue;
// For each cell
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
// Traversing thewhole matrix
// to find the minimum distance.
for (int k = 0; k < N; k++)
for (int l = 0; l < M; l++)
{
// If cell contain 1, check
// for minimum distance.
if (mat[k,l] == 1)
ans[i,j] =
Math.Min(ans[i,j],
Math.Abs(i-k)
+ Math.Abs(j-l));
}
}
// Printing the answer.
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
Console.Write( ans[i,j] + " ");
Console.WriteLine();
}
}
// Driven Program
public static void Main ()
{
int [,]mat = { {0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0} };
printDistance(mat);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find distance of nearest
// cell having 1 in a binary matrix.
$N = 3;
$M = 4;
// Print the distance of nearest cell
// having 1 for each cell.
function printDistance( $mat)
{
global $N,$M;
$ans = array(array());
// Initialize the answer
// matrix with INT_MAX.
for($i = 0; $i < $N; $i++)
for ( $j = 0; $j < $M; $j++)
$ans[$i][$j] = PHP_INT_MAX;
// For each cell
for ( $i = 0; $i < $N; $i++)
for ( $j = 0; $j < $M; $j++)
{
// Traversing the whole matrix
// to find the minimum distance.
for ($k = 0; $k < $N; $k++)
for ( $l = 0; $l < $M; $l++)
{
// If cell contain 1, check
// for minimum distance.
if ($mat[$k][$l] == 1)
$ans[$i][$j] = min($ans[$i][$j],
abs($i-$k) + abs($j - $l));
}
}
// Printing the answer.
for ( $i = 0; $i < $N; $i++)
{
for ( $j = 0; $j < $M; $j++)
echo $ans[$i][$j] , " ";
echo "\n";
}
}
// Driver Code
$mat = array(array(0, 0, 0, 1),
array(0, 0, 1, 1),
array(0, 1, 1, 0));
printDistance($mat);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find distance of nearest
// cell having 1 in a binary matrix.
let N = 3;
let M = 4;
// Print the distance of nearest cell
// having 1 for each cell.
function printDistance(mat)
{
let ans= new Array(N);
for(let i=0;i<N;i++)
{
ans[i]=new Array(M);
for(let j = 0; j < M; j++)
{
ans[i][j] = Number.MAX_VALUE;
}
}
// For each cell
for (let i = 0; i < N; i++)
for (let j = 0; j < M; j++)
{
// Traversing the whole matrix
// to find the minimum distance.
for (let k = 0; k < N; k++)
for (let l = 0; l < M; l++)
{
// If cell contain 1, check
// for minimum distance.
if (mat[k][l] == 1)
ans[i][j] =
Math.min(ans[i][j],
Math.abs(i-k)
+ Math.abs(j-l));
}
}
// Printing the answer.
for (let i = 0; i < N; i++)
{
for (let j = 0; j < M; j++)
document.write( ans[i][j] + " ");
document.write("<br>");
}
}
// Driven Program
let mat = [[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 1, 1, 0]]
printDistance(mat);
// This code is contributed by patel2127
</script>
Producción
3 2 1 0 2 1 0 0 1 0 0 1
Análisis de Complejidad:
- Complejidad Temporal: O(N 2 *M 2 ).
Para cada elemento de la array, la array se recorre y hay N*M elementos. Por lo tanto, la complejidad temporal es O(N 2 *M 2 ). - Complejidad espacial: O(1).
No se requiere espacio adicional.
Método 1(a): enfoque de fuerza bruta mejorado.
- Enfoque: La idea es cargar las coordenadas i y j de los 1 en la Array en una Cola y luego recorrer todos los elementos de la Array «0» y comparar la distancia entre todos los 1 de la Cola para obtener la distancia mínima.
- Algoritmo:
- Atraviese una vez Matrix y cargue todas las coordenadas i y j de 1 en la cola.
- Una vez cargado, atraviesa todos los elementos de Matrix. Si el elemento es «0», verifique la distancia mínima eliminando los elementos de la cola uno por uno.
- Una vez que se obtiene la distancia para un elemento «0» desde el elemento «1», vuelva a colocar las coordenadas del 1 en la cola para el siguiente elemento «0».
- Determine la distancia mínima a partir de las distancias individuales para cada elemento «0».
Implementación:
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
static class matrix_element {
int row;
int col;
matrix_element(int row, int col)
{
this.row = row;
this.col = col;
}
}
static void printDistance(int arr[][])
{
int Row_Count = arr.length;
int Col_Count = arr[0].length;
Queue<matrix_element> q
= new LinkedList<matrix_element>();
// Adding all ones in queue
for (int i = 0; i < Row_Count; i++) {
for (int j = 0; j < Col_Count; j++) {
if (arr[i][j] == 1)
q.add(new matrix_element(i, j));
}
}
// In order to find min distance we will again
// traverse all elements in Matrix. If its zero then
// it will check against all 1's in Queue. Whatever
// will be dequeued from queued, will be enqueued
// back again.
int Queue_Size = q.size();
for (int i = 0; i < Row_Count; i++)
{
for (int j = 0; j < Col_Count; j++)
{
int distance = 0;
int min_distance = Integer.MAX_VALUE;
if (arr[i][j] == 0) {
for (int k = 0; k < Queue_Size; k++)
{
matrix_element One_Pos = q.poll();
int One_Row = One_Pos.row;
int One_Col = One_Pos.col;
distance = Math.abs(One_Row - i)
+ Math.abs(One_Col - j);
min_distance = Math.min(
min_distance, distance);
if (min_distance == 1)
{
arr[i][j] = 1;
q.add(new matrix_element(
One_Row, One_Col));
break;
}
q.add(new matrix_element(One_Row,
One_Col));
}
arr[i][j] = min_distance;
}
else {
arr[i][j] = 0;
}
}
}
// print the elements
for (int i = 0; i < Row_Count; i++) {
for (int j = 0; j < Col_Count; j++)
System.out.print(arr[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args){
int arr[][]
= { { 0, 0, 0, 1 }, { 0, 0, 1, 1 }, { 0, 1, 1, 0 } };
printDistance(arr);
}
}
//// This code is contributed by prithi_raj
Python3
import sys class matrix_element: def __init__(self, row, col): self.row = row self.col = col def printDistance(arr): Row_Count = len(arr) Col_Count = len(arr[0]) q = [] # Adding all ones in queue for i in range(Row_Count): for j in range(Col_Count): if (arr[i][j] == 1): q.append(matrix_element(i, j)) # In order to find min distance we will again # traverse all elements in Matrix. If its zero then # it will check against all 1's in Queue. Whatever # will be dequeued from queued, will be enqueued # back again. Queue_Size = len(q) for i in range(Row_Count): for j in range(Col_Count): distance = 0 min_distance = sys.maxsize if (arr[i][j] == 0): for k in range(Queue_Size): One_Pos = q[0] q = q[1:] One_Row = One_Pos.row One_Col = One_Pos.col distance = abs(One_Row - i) + abs(One_Col - j) min_distance = min(min_distance, distance) if (min_distance == 1): arr[i][j] = 1 q.append(matrix_element(One_Row, One_Col)) break q.append(matrix_element(One_Row,One_Col)) arr[i][j] = min_distance else: arr[i][j] = 0 # print elements for i in range(Row_Count): for j in range(Col_Count): print(arr[i][j] ,end = " ") print() # driver code arr = [ [ 0, 0, 0, 1 ], [ 0, 0, 1, 1 ], [ 0, 1, 1, 0 ] ] printDistance(arr) # This code is contributed by shinjanpatra
Javascript
<script>
class matrix_element{
constructor(row, col){
this.row = row
this.col = col
}
}
function printDistance(arr){
let Row_Count = arr.length
let Col_Count = arr[0].length
let q = []
// Adding all ones in queue
for(let i = 0; i < Row_Count; i++){
for(let j = 0; j < Col_Count; j++){
if (arr[i][j] == 1)
q.push(new matrix_element(i, j))
}
}
// In order to find min distance we will again
// traverse all elements in Matrix. If its zero then
// it will check against all 1's in Queue. Whatever
// will be dequeued from queued, will be enqueued
// back again.
let Queue_Size = q.length
for(let i = 0; i < Row_Count; i++)
{
for(let j = 0; j < Col_Count; j++)
{
let distance = 0
let min_distance = Number.MAX_VALUE
if (arr[i][j] == 0){
for(let k = 0; k < Queue_Size; k++)
{
let One_Pos = q.shift()
let One_Row = One_Pos.row
let One_Col = One_Pos.col
distance = Math.abs(One_Row - i) + Math.abs(One_Col - j)
min_distance = Math.min(min_distance, distance)
if (min_distance == 1){
arr[i][j] = 1
q.push(new matrix_element(One_Row, One_Col))
break
}
q.push(new matrix_element(One_Row,One_Col))
arr[i][j] = min_distance
}
}
else
arr[i][j] = 0
}
}
// print elements
for(let i = 0; i < Row_Count; i++)
{
for(let j = 0; j < Col_Count; j++)
{
document.write(arr[i][j] ," ")
}
document.write("</br>")
}
}
// driver code
let arr = [ [ 0, 0, 0, 1 ], [ 0, 0, 1, 1 ], [ 0, 1, 1, 0 ] ]
printDistance(arr)
// This code is contributed by shinjanpatra
</script>
Producción
3 2 1 0 2 1 0 0 1 0 0 1
Método 2: este método utiliza la BFS o la técnica de búsqueda en amplitud para llegar a la solución.
- Enfoque: La idea es utilizar la búsqueda en amplitud de múltiples fuentes. Considere cada celda como un Node y cada límite entre dos celdas adyacentes como un borde. Numere cada celda del 1 al N*M. Ahora, empuje todos los Nodes cuyo valor de celda correspondiente sea 1 en la array en la cola. Aplique BFS usando esta cola para encontrar la distancia mínima del Node adyacente.
- Algoritmo:
- Cree un gráfico con valores asignados de 1 a M*N a todos los vértices. El propósito es almacenar la posición y la información adyacente.
- Crea una cola vacía.
- Atraviese todos los elementos de la array e inserte posiciones de todos los 1 en la cola.
- Ahora haga un recorrido BFS del gráfico utilizando la cola creada anteriormente.
- Ejecute un ciclo hasta que el tamaño de la cola sea mayor que 0, luego extraiga el Node frontal de la cola, elimínelo e inserte todos sus elementos adyacentes y sin marcar. Actualice la distancia mínima como distancia del Node actual +1 e inserte el elemento en la cola.
Implementación:
C++
// C++ program to find distance of nearest
// cell having 1 in a binary matrix.
#include<bits/stdc++.h>
#define MAX 500
#define N 3
#define M 4
using namespace std;
// Making a class of graph with bfs function.
class graph
{
private:
vector<int> g[MAX];
int n,m;
public:
graph(int a, int b)
{
n = a;
m = b;
}
// Function to create graph with N*M nodes
// considering each cell as a node and each
// boundary as an edge.
void createGraph()
{
int k = 1; // A number to be assigned to a cell
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// If last row, then add edge on right side.
if (i == n)
{
// If not bottom right cell.
if (j != m)
{
g[k].push_back(k+1);
g[k+1].push_back(k);
}
}
// If last column, then add edge toward down.
else if (j == m)
{
g[k].push_back(k+m);
g[k+m].push_back(k);
}
// Else makes an edge in all four directions.
else
{
g[k].push_back(k+1);
g[k+1].push_back(k);
g[k].push_back(k+m);
g[k+m].push_back(k);
}
k++;
}
}
}
// BFS function to find minimum distance
void bfs(bool visit[], int dist[], queue<int> q)
{
while (!q.empty())
{
int temp = q.front();
q.pop();
for (int i = 0; i < g[temp].size(); i++)
{
if (visit[g[temp][i]] != 1)
{
dist[g[temp][i]] =
min(dist[g[temp][i]], dist[temp]+1);
q.push(g[temp][i]);
visit[g[temp][i]] = 1;
}
}
}
}
// Printing the solution.
void print(int dist[])
{
for (int i = 1, c = 1; i <= n*m; i++, c++)
{
cout << dist[i] << " ";
if (c%m == 0)
cout << endl;
}
}
};
// Find minimum distance
void findMinDistance(bool mat[N][M])
{
// Creating a graph with nodes values assigned
// from 1 to N x M and matrix adjacent.
graph g1(N, M);
g1.createGraph();
// To store minimum distance
int dist[MAX];
// To mark each node as visited or not in BFS
bool visit[MAX] = { 0 };
// Initialising the value of distance and visit.
for (int i = 1; i <= M*N; i++)
{
dist[i] = INT_MAX;
visit[i] = 0;
}
// Inserting nodes whose value in matrix
// is 1 in the queue.
int k = 1;
queue<int> q;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (mat[i][j] == 1)
{
dist[k] = 0;
visit[k] = 1;
q.push(k);
}
k++;
}
}
// Calling for Bfs with given Queue.
g1.bfs(visit, dist, q);
// Printing the solution.
g1.print(dist);
}
// Driven Program
int main()
{
bool mat[N][M] =
{
0, 0, 0, 1,
0, 0, 1, 1,
0, 1, 1, 0
};
findMinDistance(mat);
return 0;
}
Python3
# Python3 program to find distance of nearest # cell having 1 in a binary matrix. from collections import deque MAX = 500 N = 3 M = 4 # Making a class of graph with bfs function. g = [[] for i in range(MAX)] n, m = 0, 0 # Function to create graph with N*M nodes # considering each cell as a node and each # boundary as an edge. def createGraph(): global g, n, m # A number to be assigned to a cell k = 1 for i in range(1, n + 1): for j in range(1, m + 1): # If last row, then add edge on right side. if (i == n): # If not bottom right cell. if (j != m): g[k].append(k + 1) g[k + 1].append(k) # If last column, then add edge toward down. elif (j == m): g[k].append(k+m) g[k + m].append(k) # Else makes an edge in all four directions. else: g[k].append(k + 1) g[k + 1].append(k) g[k].append(k+m) g[k + m].append(k) k += 1 # BFS function to find minimum distance def bfs(visit, dist, q): global g while (len(q) > 0): temp = q.popleft() for i in g[temp]: if (visit[i] != 1): dist[i] = min(dist[i], dist[temp] + 1) q.append(i) visit[i] = 1 return dist # Printing the solution. def prt(dist): c = 1 for i in range(1, n * m + 1): print(dist[i], end = " ") if (c % m == 0): print() c += 1 # Find minimum distance def findMinDistance(mat): global g, n, m # Creating a graph with nodes values assigned # from 1 to N x M and matrix adjacent. n, m = N, M createGraph() # To store minimum distance dist = [0] * MAX # To mark each node as visited or not in BFS visit = [0] * MAX # Initialising the value of distance and visit. for i in range(1, M * N + 1): dist[i] = 10**9 visit[i] = 0 # Inserting nodes whose value in matrix # is 1 in the queue. k = 1 q = deque() for i in range(N): for j in range(M): if (mat[i][j] == 1): dist[k] = 0 visit[k] = 1 q.append(k) k += 1 # Calling for Bfs with given Queue. dist = bfs(visit, dist, q) # Printing the solution. prt(dist) # Driver code if __name__ == '__main__': mat = [ [ 0, 0, 0, 1 ], [ 0, 0, 1, 1 ], [ 0, 1, 1, 0 ] ] findMinDistance(mat) # This code is contributed by mohit kumar 29
Producción
3 2 1 0 2 1 0 0 1 0 0 1
Análisis de Complejidad:
- Complejidad de tiempo: O(N*M) .
En el recorrido BFS, cada elemento se atraviesa solo una vez, por lo que la complejidad del tiempo es O (M * N). - Complejidad espacial: O(M*N).
Para almacenar cada elemento en la array O(M*N) se requiere espacio.
Este artículo es una contribución de Anuj Chauhan . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA