Dada una array binaria de orden m*n, la tarea es encontrar la distancia del 1 más cercano para cada 0 en la array e imprimir la array de distancia final. Desde cualquier celda (i, j), podemos movernos solo en cuatro direcciones arriba, abajo, izquierda y derecha.
Nota: La distancia de una celda a otra celda inmediata siempre se incrementa en 1.
Ejemplos:
Input : m = 3, n = 4
mat[m][n] = {{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
Una solución simple de fuerza bruta para este problema es, para cada 0 en la array, llamar recursivamente a la función DFS o BFS para verificar el 1 más cercano en la array.
Aquí estamos usando el enfoque dfs para calcular la distancia del ‘1’ más cercano.
Implementación: A continuación se muestra la implementación del algoritmo anterior.
C++
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// distance matrix which stores the distance of
// nearest '1'
int dist[MAX][MAX];
int dfs(int mat[][MAX], int m, int n,int i,int j,vector<vector<bool>> visited)
{
// here we are validating if current coordinate is
// out of bound or already visited or not
if(i<0||j<0||i>=m||j>=n||visited[i][j]==true)
return MAX;
//we reach the cell having 1 so, return
if(mat[i][j]==1) return 0;
//otherwise first mark current coordinate visited
visited[i][j]=true;
// checking using dfs in all four direction to get min for the
// nearest 1 +1 for the current cell
int val=1+min(dfs(mat,m,n,i+1,j,visited),min(dfs(mat,m,n,i-1,j,visited),
min(dfs(mat,m,n,i,j+1,visited),dfs(mat,m,n,i,j-1,visited))));
//backtrack so that other path when reach can use this cell
visited[i][j]=false;
return val;
}
// Function to find the nearest '1'
void nearestOne(int mat[][MAX], int m, int n)
{
vector<vector<bool>> visited(m,vector<bool>(n,false));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j]==0)
dist[i][j]=dfs(mat,m,n,i,j,visited);
}
}
return;
}
int main()
{
int m = 3, n = 4;
int mat[][MAX] = {{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0}
};
// Fills values in dist[][]
nearestOne(mat, m, n);
// print distance matrix
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
cout << dist[i][j] << " ";
cout << endl;
}
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static int MAX = 1000;
// distance matrix which stores the distance of
// nearest '1'
static int dist[][] = new int[MAX][MAX];
static int dfs(int mat[][], int m, int n,int i,int j,boolean visited[][])
{
//here we are validating if current
// coordinate is out of bound or already visited or not
if(i < 0 || j < 0 || i >= m ||
j >= n || visited[i][j] == true)
return MAX;
//we reach the cell having 1 so, return
if(mat[i][j] == 1) return 0;
//otherwise first mark current coordinate visited
visited[i][j] = true;
//checking using dfs in all four direction
// to get min for the nearest 1 +1 for the current cell
int val=1+Math.min(dfs(mat, m, n, i + 1, j, visited),
Math.min(dfs(mat, m, n, i - 1, j, visited),
Math.min(dfs(mat, m, n, i, j + 1, visited),
dfs(mat, m, n, i, j - 1, visited))));
//backtrack so that other path when reach can use this cell
visited[i][j] = false;
return val;
}
// Function to find the nearest '1'
static void nearestOne(int mat[][], int m, int n)
{
boolean visited[][] = new boolean[m][n];
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
visited[i][j] = false;
}
}
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(mat[i][j] == 0)
dist[i][j] = dfs(mat, m, n, i, j, visited);
}
}
return;
}
// Driver Code
public static void main(String args[])
{
int m = 3, n = 4;
int mat[][] = {{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0}
};
// Fills values in dist[][]
nearestOne(mat, m, n);
// print distance matrix
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
System.out.print(dist[i][j] + " ");
System.out.println();
}
}
}
// This code is contributed by shinjanpatra
Producción
3 2 1 0 2 1 0 0 1 0 0 1
Complejidad del tiempo : la complejidad del tiempo del algoritmo anterior es O(m*n)*O(m+n), donde m y n son no. de filas y columnas de la array. ya que hemos usado dos bucles para atravesar cada celda de la array que tomará O(m*n) y para llamar a la función DFS para la celda que tiene 0 que tomará O(m+n). En el peor de los casos, toda la celda contiene 0. entonces, tenemos que llamar a la función DFS para cada celda, lo que aumenta la complejidad del tiempo.
Por lo tanto, este algoritmo podría dar un límite de tiempo excedido para algunos de los casos de prueba.
Una solución eficiente para este problema es utilizar BFS . Aquí está el algoritmo para resolver este problema:
- Tome la array de distancia dist[m][n] e inicialícela con INT_MAX.
- Ahora recorra la array y haga_par(i,j) de índices de celda (i,j) que tengan el valor ‘1’ y empuje este par a la cola y actualice dist[i][j] = 0 porque la distancia de ‘1’ de sí mismo será siempre 0.
- Ahora extraiga los elementos de la cola uno por uno hasta que se vacíe y llame a BFS .
- Aquí necesitamos encontrar la distancia del más cercano y estamos llamando a BFS para las celdas que tienen ‘1’, por lo que cada vez que tomamos elementos adyacentes de la cola, tratamos de minimizar la distancia poniendo la condición si (dist[i][ j]+1) < dist[ADCi][ADCj]. Luego, actualizamos la distancia del elemento adyacente en la array de distancia y empujamos este elemento adyacente en la cola para completar el recorrido BFS y llenar la array de distancia completa.
- Después de completar el recorrido BFS , cada celda de la array de distancia contendrá la distancia del ‘1’ más cercano.
Implementación:
C++
// C++ program to find the minimum distance from a
// "1" in binary matrix.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// distance matrix which stores the distance of
// nearest '1'
int dist[MAX][MAX];
// Function to find the nearest '1'
void nearestOne(int mat[][MAX], int m, int n)
{
// two array when respective values of newx and
// newy are added to (i,j) it gives up, down,
// left or right adjacent of (i,j) cell
int newx[] = { -1, 0, 1, 0 };
int newy[] = { 0, -1, 0, 1 };
// queue of pairs to store nodes for bfs
queue<pair<int, int> > q;
// traverse matrix and make pair of indices of
// cell (i,j) having value '1' and push them
// in queue
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INT_MAX;
if (mat[i][j] == 1) {
// distance of '1' from itself is always 0
dist[i][j] = 0;
// make pair and push it in queue
q.push(make_pair(i, j));
}
}
}
// now do bfs traversal
// pop element from queue one by one until it gets empty
// pair element to hold the currently popped element
pair<int, int> poped;
while (!q.empty()) {
poped = q.front();
q.pop();
// coordinate of currently popped node
int x = poped.first;
int y = poped.second;
// now check for all adjacent of popped element
for (int i = 0; i < 4; i++) {
int adjx = x + newx[i];
int adjy = y + newy[i];
// if new coordinates are within boundary and
// we can minimize the distance of adjacent
// then update the distance of adjacent in
// distance matrix and push this adjacent
// element in queue for further bfs
if (adjx >= 0 && adjx < m && adjy >= 0
&& adjy < n
&& dist[adjx][adjy] > dist[x][y] + 1) {
// update distance
dist[adjx][adjy] = dist[x][y] + 1;
q.push(make_pair(adjx, adjy));
}
}
}
}
// Driver program to run the case
int main()
{
int m = 3, n = 4;
int mat[][MAX] = { { 0, 0, 0, 1 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 } };
// Fills values in dist[][]
nearestOne(mat, m, n);
// print distance matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
cout << dist[i][j] << " ";
cout << endl;
}
return 0;
}
Python3
# Python3 program to find the minimum distance from a # "1" in binary matrix. MAX = 1000 INT_MAX = (2**32) # distance matrix which stores the distance of # nearest '1' dist = [[0 for i in range(MAX)] for j in range(MAX)] # Function to find the nearest '1' def nearestOne(mat, m, n): # two array when respective values of newx and # newy are added to (i,j) it gives up, down, # left or right adjacent of (i,j) cell newx = [-1, 0, 1, 0] newy = [0, -1, 0, 1] # queue of pairs to store nodes for bfs q = [] # traverse matrix and make pair of indices of # cell (i,j) having value '1' and push them # in queue for i in range(m): for j in range(n): dist[i][j] = INT_MAX if (mat[i][j] == 1): # distance of '1' from itself is always 0 dist[i][j] = 0 # make pair and push it in queue q.append([i, j]) # now do bfs traversal # pop element from queue one by one until it gets empty # pair element to hold the currently popped element poped = [] while (len(q)): poped = q[0] q.pop(0) # coordinate of currently popped node x = poped[0] y = poped[1] # now check for all adjacent of popped element for i in range(4): adjx = x + newx[i] adjy = y + newy[i] # if new coordinates are within boundary and # we can minimize the distance of adjacent # then update the distance of adjacent in # distance matrix and push this adjacent # element in queue for further bfs if (adjx >= 0 and adjx < m and adjy >= 0 and adjy < n and dist[adjx][adjy] > dist[x][y] + 1): # update distance dist[adjx][adjy] = dist[x][y] + 1 q.append([adjx, adjy]) # Driver code m = 3 n = 4 mat = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 0]] # Fills values in dist[][] nearestOne(mat, m, n) # print distance matrix for i in range(m): for j in range(n): print(dist[i][j], end=" ") print() # This code is contributed by shubhamsingh10
Javascript
<script>
// JavaScript program to find the minimum distance from a
// "1" in binary matrix.
const MAX = 1000
INT_MAX = (2**32)
// distance matrix which stores the distance of
// nearest '1'
let dist = new Array(MAX).fill(0).map(()=>new Array(MAX).fill(0))
// Function to find the nearest '1'
function nearestOne(mat, m, n){
// two array when respective values of newx and
// newy are added to (i,j) it gives up, down,
// left or right adjacent of (i,j) cell
let newx = [-1, 0, 1, 0]
let newy = [0, -1, 0, 1]
// queue of pairs to store nodes for bfs
let q = []
// traverse matrix and make pair of indices of
// cell (i,j) having value '1' and push them
// in queue
for(let i=0;i<m;i++){
for(let j=0;j<n;j++){
dist[i][j] = INT_MAX
if (mat[i][j] == 1){
// distance of '1' from itself is always 0
dist[i][j] = 0
// make pair and push it in queue
q.push([i, j])
}
}
}
// now do bfs traversal
// pop element from queue one by one until it gets empty
// pair element to hold the currently popped element
let poped = []
while (q.length){
poped = q.shift()
// coordinate of currently popped node
let x = poped[0]
let y = poped[1]
// now check for all adjacent of popped element
for(let i=0;i<4;i++){
let adjx = x + newx[i]
let adjy = y + newy[i]
// if new coordinates are within boundary and
// we can minimize the distance of adjacent
// then update the distance of adjacent in
// distance matrix and push this adjacent
// element in queue for further bfs
if (adjx >= 0 && adjx < m && adjy >= 0 &&
adjy < n && dist[adjx][adjy] > dist[x][y] + 1){
// update distance
dist[adjx][adjy] = dist[x][y] + 1
q.push([adjx, adjy])
}
}
}
}
// Driver code
let m = 3
let n = 4
let mat= [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 0]]
// Fills values in dist[][]
nearestOne(mat, m, n)
// print distance matrix
for(let i=0;i<m;i++){
for(let j=0;j<n;j++){
document.write(dist[i][j]," ")
}
document.write("</br>")
}
// This code is contributed by shinjanpatra
</script>
Producción
3 2 1 0 2 1 0 0 1 0 0 1
Dado que no podemos hacerlo mejor que la complejidad del tiempo O (m * n), pero aún podemos hacerlo mejor en la complejidad del espacio con el espacio O (1).
La lógica detrás de este algoritmo es que, si en cualquier celda, conocemos la distancia de sus cuatro celdas de dirección, solo tenemos que tomar el mínimo de las cuatro direcciones más 1 para calcular la celda actual.
Tenemos que calcular de arriba a abajo y de izquierda a derecha para cada celda, pero esto quedará sin calcular para las celdas de la parte inferior derecha. Entonces, ejecutamos este enfoque en 2 fases, si obtenemos 1, llenamos ciegamente 0 ya que la distancia de 1 con 1 es 0; de lo contrario, tomamos el mínimo de la celda superior e izquierda y le agregamos 1.
Ahora, vuelva a ejecutar dos bucles y calcule la celda de abajo a arriba y de derecha a izquierda, pero aquí, en lugar de tomar a ciegas el mínimo de abajo y la derecha, tomaremos el mínimo del valor actual de la celda, la derecha y la parte inferior y le agregaremos 1.
Implementación:
C++
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Function to find the nearest '1'
void nearestOne(int mat[][MAX], int m, int n)
{
//top to bottom and left to right
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j]==0)
{
int top=i-1>=0 ? mat[i-1][j]:MAX;
int left=j-1>=0? mat[i][j-1]:MAX;
mat[i][j]=min(top,left)+1;
}
//As distance between cell having 1 with nearest cell 1 is 0
else
{
mat[i][j]=0;
}
}
}
//bottom to top and right to left
for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=0;j--)
{
int bottom=i+1<m? mat[i+1][j]:MAX;
int right=j+1<n? mat[i][j+1]:MAX;
mat[i][j]=min(mat[i][j],min(bottom,right)+1);
}
}
return;
}
int main()
{
int m = 3, n = 4;
int mat[][MAX] = {{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0}
};
// solution distance is updated in mat[][]
nearestOne(mat, m, n);
// print distance
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
cout << mat[i][j] << " ";
cout << endl;
}
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
public static int MAX = 1000;
public static void nearestOne(int mat[][], int m, int n)
{
//top to bottom and left to right
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(mat[i][j] == 0)
{
int top = i - 1 >= 0 ? mat[i - 1][j]:MAX;
int left = j - 1 >= 0? mat[i][j - 1]:MAX;
mat[i][j] = Math.min(top,left) + 1;
}
//As distance between cell having 1 with nearest cell 1 is 0
else
{
mat[i][j] = 0;
}
}
}
//bottom to top and right to left
for(int i = m - 1; i >= 0; i--)
{
for(int j = n - 1; j >= 0; j--)
{
int bottom = i + 1<m? mat[i+1][j]:MAX;
int right = j + 1<n? mat[i][j+1]:MAX;
mat[i][j] = Math.min(mat[i][j],Math.min(bottom,right)+1);
}
}
return;
}
public static void main (String[] args)
{
int m = 3, n = 4;
int[][] mat = { {0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0} };
// solution distance is updated in mat[][]
nearestOne(mat, m, n);
// print distance
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
System.out.print(mat[i][j] + " ");
System.out.print("\n");
}
}
}
// This code is contributed by kothavvsaakash.
Producción
3 2 1 0 2 1 0 0 1 0 0 1
Este artículo es una contribución de Shashank Mishra (Gullu) . 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