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;
}
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, 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.
Python3
# Python3 Code implementation for above problem
# QItem for current location and distance
# from source location
class QItem:
def __init__(self, row, col, dist):
self.row = row
self.col = col
self.dist = dist
def __repr__(self):
return f"QItem({self.row}, {self.col}, {self.dist})"
def minDistance(grid):
source = QItem(0, 0, 0)
# Finding the source to start from
for row in range(len(grid)):
for col in range(len(grid[row])):
if grid[row][col] == 's':
source.row = row
source.col = col
break
# To maintain location visit status
visited = [[False for _ in range(len(grid[0]))]
for _ in range(len(grid))]
# applying BFS on matrix cells starting from source
queue = []
queue.append(source)
visited[source.row][source.col] = True
while len(queue) != 0:
source = queue.pop(0)
# Destination found;
if (grid[source.row][source.col] == 'd'):
return source.dist
# moving up
if isValid(source.row - 1, source.col, grid, visited):
queue.append(QItem(source.row - 1, source.col, source.dist + 1))
visited[source.row - 1][source.col] = True
# moving down
if isValid(source.row + 1, source.col, grid, visited):
queue.append(QItem(source.row + 1, source.col, source.dist + 1))
visited[source.row + 1][source.col] = True
# moving left
if isValid(source.row, source.col - 1, grid, visited):
queue.append(QItem(source.row, source.col - 1, source.dist + 1))
visited[source.row][source.col - 1] = True
# moving right
if isValid(source.row, source.col + 1, grid, visited):
queue.append(QItem(source.row, source.col + 1, source.dist + 1))
visited[source.row][source.col + 1] = True
return -1
# checking where move is valid or not
def isValid(x, y, grid, visited):
if ((x >= 0 and y >= 0) and
(x < len(grid) and y < len(grid[0])) and
(grid[x][y] != '0') and (visited[x][y] == False)):
return True
return False
# Driver code
if __name__ == '__main__':
grid = [['0', '*', '0', 's'],
['*', '0', '*', '*'],
['0', '*', '*', '*'],
['d', '*', '*', '*']]
print(minDistance(grid))
# This code is contributed by sajalmittaldei.
C#
using System;
using System.Collections.Generic;
// C# Code implementation for above problem
// QItem for current location and distance
// from source location
public class QItem {
public int row;
public int col;
public int dist;
public QItem(int x, int y, int w)
{
this.row = x;
this.col = y;
this.dist = w;
}
}
public static class GFG {
static int N = 4;
static int M = 4;
public static int minDistance(char[, ] grid)
{
QItem source = new QItem(0, 0, 0);
// To keep track of visited QItems. Marking
// blocked cells as visited.
bool[, ] visited = new bool[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 = new Queue<QItem>();
q.Enqueue(source);
visited[source.row, source.col] = true;
while (q.Count > 0) {
QItem p = q.Peek();
q.Dequeue();
// 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.Enqueue(new 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.Enqueue(new 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.Enqueue(new 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.Enqueue(new QItem(p.row, p.col + 1,
p.dist + 1));
visited[p.row, p.col + 1] = true;
}
}
return -1;
}
// Driver code
public static void Main()
{
char[, ] grid = { { '0', '*', '0', 's' },
{ '*', '0', '*', '*' },
{ '0', '*', '*', '*' },
{ 'd', '*', '*', '*' } };
Console.Write(minDistance(grid));
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// Javascript Code implementation for above problem
var N = 4;
var M = 4;
// QItem for current location and distance
// from source location
class QItem {
constructor(x, y, w)
{
this.row = x;
this.col = y;
this.dist = w;
}
};
function minDistance(grid)
{
var source = new QItem(0, 0, 0);
// To keep track of visited QItems. Marking
// blocked cells as visited.
var visited = Array.from(Array(N), ()=>Array(M).fill(0));
for (var i = 0; i < N; i++) {
for (var 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
var q = [];
q.push(source);
visited[source.row][source.col] = true;
while (q.length!=0) {
var p = q[0];
q.shift();
// 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(new 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(new 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(new 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(new QItem(p.row, p.col + 1, p.dist + 1));
visited[p.row][p.col + 1] = true;
}
}
return -1;
}
// Driver code
var grid = [ [ '0', '*', '0', 's' ],
[ '*', '0', '*', '*' ],
[ '0', '*', '*', '*' ],
[ 'd', '*', '*', '*' ] ];
document.write(minDistance(grid));
// This code is contributed by rrrtnx.
</script>
Producción
6
Complejidad temporal: O(N x M)
Espacio auxiliar: O(N x M)
Este artículo es una contribución de Aarti_Rathi y Prashant Singh . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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