Dada una array de orden N*M. Encuentre la distancia más corta desde una celda de origen hasta una celda de destino, atravesando solo celdas limitadas. También puedes moverte solo hacia arriba, abajo, izquierda y derecha. Si se encuentra, emite la distancia más -1.
s representa ‘fuente’
d representa ‘destino’
* representa celda por la que puede viajar
0 representa celda por la que no puede viajar
Este problema está diseñado para una sola fuente y destino.
Ejemplos:
Input : {'0', '*', '0', 's'},
{'*', '0', '*', '*'},
{'0', '*', '*', '*'},
{'d', '*', '*', '*'}
Output : 6
Input : {'0', '*', '0', 's'},
{'*', '0', '*', '*'},
{'0', '*', '*', '*'},
{'d', '0', '0', '0'}
Output : -1
La idea es BFS (búsqueda primero en amplitud) en celdas de array. Tenga en cuenta que siempre podemos usar BFS para encontrar la ruta más corta si el gráfico no está ponderado.
- Almacene cada celda como un Node con sus valores de fila, columna y distancia desde la celda de origen.
- Inicie BFS con la celda de origen.
- Cree una array visitada en la que todos tengan valores «falsos», excepto las celdas ‘0’, a las que se les asignan valores «verdaderos», ya que no se pueden atravesar.
- Siga actualizando la distancia desde el valor de la fuente en cada movimiento.
- Devuelve la distancia cuando se cumple el destino, de lo contrario, devuelve -1 (no existe una ruta entre el origen y el destino).
Java
/*package whatever //do not write package name here */
// Java Code implementation for above problem
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
// QItem for current location and distance
// from source location
class QItem {
int row;
int col;
int dist;
public QItem(int row, int col, int dist)
{
this.row = row;
this.col = col;
this.dist = dist;
}
}
public class Maze {
private static int minDistance(char[][] grid)
{
QItem source = new QItem(0, 0, 0);
// To keep track of visited QItems. Marking
// blocked cells as visited.
firstLoop:
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++)
{
// Finding source
if (grid[i][j] == 's') {
source.row = i;
source.col = j;
break firstLoop;
}
}
}
// applying BFS on matrix cells starting from source
Queue<QItem> queue = new LinkedList<>();
queue.add(new QItem(source.row, source.col, 0));
boolean[][] visited
= new boolean[grid.length][grid[0].length];
visited[source.row][source.col] = true;
while (queue.isEmpty() == false) {
QItem p = queue.remove();
// Destination found;
if (grid[p.row][p.col] == 'd')
return p.dist;
// moving up
if (isValid(p.row - 1, p.col, grid, visited)) {
queue.add(new QItem(p.row - 1, p.col,
p.dist + 1));
visited[p.row - 1][p.col] = true;
}
// moving down
if (isValid(p.row + 1, p.col, grid, visited)) {
queue.add(new QItem(p.row + 1, p.col,
p.dist + 1));
visited[p.row + 1][p.col] = true;
}
// moving left
if (isValid(p.row, p.col - 1, grid, visited)) {
queue.add(new QItem(p.row, p.col - 1,
p.dist + 1));
visited[p.row][p.col - 1] = true;
}
// moving right
if (isValid(p.row - 1, p.col + 1, grid,
visited)) {
queue.add(new QItem(p.row, p.col + 1,
p.dist + 1));
visited[p.row][p.col + 1] = true;
}
}
return -1;
}
// checking where it's valid or not
private static boolean isValid(int x, int y,
char[][] grid,
boolean[][] visited)
{
if (x >= 0 && y >= 0 && x < grid.length
&& y < grid[0].length && grid[x][y] != '0'
&& visited[x][y] == false) {
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
char[][] grid = { { '0', '*', '0', 's' },
{ '*', '0', '*', '*' },
{ '0', '*', '*', '*' },
{ 'd', '*', '*', '*' } };
System.out.println(minDistance(grid));
}
}
// This code is contributed by abhikelge21.
Producción:
6
¡Consulte el artículo completo sobre la distancia más corta entre dos celdas en una array o cuadrícula para obtener más detalles!
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