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).
CPP
// C++ Code implementation for above problem
#include <bits/stdc++.h>
using namespace std;
#define N 4
#define M 4
// QItem for current location and distance
// from source location
class QItem {
public:
int row;
int col;
int dist;
QItem(int x, int y, int w)
: row(x), col(y), dist(w)
{
}
};
int minDistance(char grid[N][M])
{
QItem source(0, 0, 0);
// To keep track of visited QItems. Marking
// blocked cells as visited.
bool visited[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
{
if (grid[i][j] == '0')
visited[i][j] = true;
else
visited[i][j] = false;
// Finding source
if (grid[i][j] == 's')
{
source.row = i;
source.col = j;
}
}
}
// applying BFS on matrix cells starting from source
queue<QItem> q;
q.push(source);
visited[source.row][source.col] = true;
while (!q.empty()) {
QItem p = q.front();
q.pop();
// Destination found;
if (grid[p.row][p.col] == 'd')
return p.dist;
// moving up
if (p.row - 1 >= 0 &&
visited[p.row - 1][p.col] == false) {
q.push(QItem(p.row - 1, p.col, p.dist + 1));
visited[p.row - 1][p.col] = true;
}
// moving down
if (p.row + 1 < N &&
visited[p.row + 1][p.col] == false) {
q.push(QItem(p.row + 1, p.col, p.dist + 1));
visited[p.row + 1][p.col] = true;
}
// moving left
if (p.col - 1 >= 0 &&
visited[p.row][p.col - 1] == false) {
q.push(QItem(p.row, p.col - 1, p.dist + 1));
visited[p.row][p.col - 1] = true;
}
// moving right
if (p.col + 1 < M &&
visited[p.row][p.col + 1] == false) {
q.push(QItem(p.row, p.col + 1, p.dist + 1));
visited[p.row][p.col + 1] = true;
}
}
return -1;
}
// Driver code
int main()
{
char grid[N][M] = { { '0', '*', '0', 's' },
{ '*', '0', '*', '*' },
{ '0', '*', '*', '*' },
{ 'd', '*', '*', '*' } };
cout << minDistance(grid);
return 0;
}
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