Dada una array binaria mat[][] de dimensiones N * M y pares de enteros src y dest que representan celdas de origen y destino respectivamente, la tarea es encontrar la secuencia más corta de movimientos desde la celda de origen dada a la celda de destino a través de celdas que consta sólo de 1 s. Los movimientos permitidos son mover una celda hacia la izquierda ( L ), derecha ( R ), arriba ( U ) y abajo ( D ) ( si existe ). Si no existe tal ruta, imprima“-1” . De lo contrario, imprima la secuencia de movimientos.
Ejemplos:
Entrada: mat[][] = {{‘0’, ‘0’, ‘0’, ‘0’, ‘0’, ‘0’}, {‘0’, ‘1’, ‘1’, ‘1 ‘, ‘1’, ‘0’}, {‘0’, ‘1’, ‘0’, ‘1’, ‘1’, ‘1’}, {‘0’, ‘1’, ‘1’, ‘1’, ‘1’, ‘0’}, {‘0’, ‘0’, ‘0’, ‘0’, ‘0’, ‘0’}}, origen = {1, 2}, destino = {2, 4}
Salida: LDDRRRU
Explicación:
La siguiente secuencia de movimientos desde la celda de origen (1, 2) hasta la celda de destino (2, 4) es la ruta más corta posible:
(1, 2) -> (1, 1 ) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4) -> (2, 4)
inicio -> Izquierda -> Abajo -> Abajo -> Derecha -> Derecha -> Derecha -> Arriba
Por lo tanto, la ruta resultante es LDDRRRRU .Entrada: mat[][] = {{‘0’, ‘1’, ‘0’, ‘1’}, {‘1’, ‘0’, ‘1’, ‘1’}, {‘1’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘0’, ‘0’, ‘0’}}, src = {0, 3}, destino = {3, 0}
Salida: DDLLLD
Enfoque: el problema dado se puede resolver realizando BFS Traversal en la array dada desde la celda de origen dada hasta la celda de destino.
Siga los pasos a continuación para resolver el problema dado:
- Inicialice una cola requerida para realizar BFS Traversal en la array dada.
- Inicialice una array booleana, digamos visited[N][M] , que se utiliza para verificar si una celda dada es visitada o no. Inicialmente, establezca todos los índices como falsos .
- Inicialice otra array, digamos distance[N][M] , que se usa para almacenar la distancia más corta desde el Node de origen hasta cada celda. Inicialícelo como -1 .
- Inicialice una string pathMoves como «» para almacenar la ruta desde el origen hasta la celda de destino .
- Empuje el Node de origen a la cola con la distancia como 0 .
- Iterar hasta que la cola no esté vacía y realizar los siguientes pasos:
- Haga estallar el Node frontal de la cola , diga currentNode .
- Compruebe si el Node extraído es el Node de destino o no. Si es cierto, encuentre la ruta desde la celda de destino hasta la celda de origen usando Backtracking .
- De lo contrario, inserte todas las celdas adyacentes no visitadas del Node emergente actual con distancia como (distancia anterior + 1) . Actualice el valor de la distancia [currentNode.x][currentNode.y] como (currentDistance + 1) .
- Después de completar los pasos anteriores, si la ruta existe desde el origen dado hasta la celda de destino, imprima la ruta almacenada en pathMoves como resultado. De lo contrario, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 4
// Stores the coordinates
// of the matrix cell
struct Point {
int x, y;
};
// Stores coordinates of
// a cell and its distance
struct Node {
Point pt;
int dist;
};
// Check if the given cell is valid or not
bool isValid(int row, int col)
{
return (row >= 0) && (col >= 0)
&& (row < ROW) && (col < COL);
}
// Stores the moves of the directions of adjacent cells
int dRow[] = { -1, 0, 0, 1 };
int dCol[] = { 0, -1, 1, 0 };
// Function to find the shortest path from the
// source to destination in the given matrix
void pathMoves(char mat[][COL],
Point src, Point dest)
{
// Stores the distance for each
// cell from the source cell
int d[ROW][COL];
memset(d, -1, sizeof d);
// Distance of source cell is 0
d[src.x][src.y] = 0;
// Initialize a visited array
bool visited[ROW][COL];
memset(visited, false, sizeof visited);
// Mark source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
queue<Node> q;
// Distance of source cell is 0
Node s = { src, 0 };
// Enqueue source cell
q.push(s);
// Keeps track of whether
// destination is reached or not
bool ok = false;
// Iterate until queue is not empty
while (!q.empty()) {
// Deque front of the queue
Node curr = q.front();
Point pt = curr.pt;
// If the destination cell is
// reached, then find the path
if (pt.x == dest.x
&& pt.y == dest.y) {
int xx = pt.x, yy = pt.y;
int dist = curr.dist;
// Assign the distance of
// destination to the
// distance matrix
d[pt.x][pt.y] = dist;
// Stores the smallest path
string pathmoves = "";
// Iterate until source is reached
while (xx != src.x
|| yy != src.y) {
// Append D
if (xx > 0 && d[xx - 1][yy] == dist - 1) {
pathmoves += 'D';
xx--;
}
// Append U
if (xx < ROW - 1
&& d[xx + 1][yy]
== dist - 1) {
pathmoves += 'U';
xx++;
}
// Append R
if (yy > 0 && d[xx][yy - 1] == dist - 1) {
pathmoves += 'R';
yy--;
}
// Append L
if (yy < COL - 1
&& d[xx][yy + 1]
== dist - 1) {
pathmoves += 'L';
yy++;
}
dist--;
}
// Reverse the backtracked path
reverse(pathmoves.begin(),
pathmoves.end());
cout << pathmoves;
ok = true;
break;
}
// Pop the start of queue
q.pop();
// Explore all adjacent directions
for (int i = 0; i < 4; i++) {
int row = pt.x + dRow[i];
int col = pt.y + dCol[i];
// If the current cell is valid
// cell and can be traversed
if (isValid(row, col)
&& (mat[row][col] == '1'
|| mat[row][col] == 's'
|| mat[row][col] == 'd')
&& !visited[row][col]) {
// Mark the adjacent cells as visited
visited[row][col] = true;
// Enqueue the adjacent cells
Node adjCell
= { { row, col }, curr.dist + 1 };
q.push(adjCell);
// Update the distance
// of the adjacent cells
d[row][col] = curr.dist + 1;
}
}
}
// If the destination
// is not reachable
if (!ok)
cout << -1;
}
// Driver Code
int main()
{
char mat[ROW][COL] = { { '0', '1', '0', '1' },
{ '1', '0', '1', '1' },
{ '0', '1', '1', '1' },
{ '1', '1', '1', '0' } };
Point src = { 0, 3 };
Point dest = { 3, 0 };
pathMoves(mat, src, dest);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
static int ROW;
static int COL;
// Stores the coordinates
// of the matrix cell
static class Point
{
int x, y;
Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Stores coordinates of
// a cell and its distance
static class Node
{
Point pt;
int dist;
Node(Point p, int dist)
{
this.pt = p;
this.dist = dist;
}
}
// Check if the given cell is valid or not
static boolean isValid(int row, int col)
{
return (row >= 0) && (col >= 0) &&
(row < ROW) && (col < COL);
}
// Stores the moves of the directions
// of adjacent cells
static int dRow[] = { -1, 0, 0, 1 };
static int dCol[] = { 0, -1, 1, 0 };
// Function to find the shortest path from the
// source to destination in the given matrix
static void pathMoves(char mat[][], Point src,
Point dest)
{
// Stores the distance for each
// cell from the source cell
int d[][] = new int[ROW][COL];
for(int dd[] : d)
Arrays.fill(dd, -1);
// Distance of source cell is 0
d[src.x][src.y] = 0;
// Initialize a visited array
boolean visited[][] = new boolean[ROW][COL];
// Mark source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
ArrayDeque<Node> q = new ArrayDeque<>();
// Distance of source cell is 0
Node s = new Node(src, 0);
// Enqueue source cell
q.addLast(s);
// Keeps track of whether
// destination is reached or not
boolean ok = false;
// Iterate until queue is not empty
while (!q.isEmpty())
{
// Deque front of the queue
Node curr = q.removeFirst();
Point pt = curr.pt;
// If the destination cell is
// reached, then find the path
if (pt.x == dest.x && pt.y == dest.y)
{
int xx = pt.x, yy = pt.y;
int dist = curr.dist;
// Assign the distance of
// destination to the
// distance matrix
d[pt.x][pt.y] = dist;
// Stores the smallest path
String pathmoves = "";
// Iterate until source is reached
while (xx != src.x || yy != src.y)
{
// Append D
if (xx > 0 &&
d[xx - 1][yy] == dist - 1)
{
pathmoves += 'D';
xx--;
}
// Append U
if (xx < ROW - 1 &&
d[xx + 1][yy] == dist - 1)
{
pathmoves += 'U';
xx++;
}
// Append R
if (yy > 0 &&
d[xx][yy - 1] == dist - 1)
{
pathmoves += 'R';
yy--;
}
// Append L
if (yy < COL - 1 &&
d[xx][yy + 1] == dist - 1)
{
pathmoves += 'L';
yy++;
}
dist--;
}
// Print reverse the backtracked path
for(int i = pathmoves.length() - 1;
i >= 0; --i)
System.out.print(pathmoves.charAt(i));
ok = true;
break;
}
// Pop the start of queue
if (!q.isEmpty())
q.removeFirst();
// Explore all adjacent directions
for(int i = 0; i < 4; i++)
{
int row = pt.x + dRow[i];
int col = pt.y + dCol[i];
// If the current cell is valid
// cell and can be traversed
if (isValid(row, col) &&
(mat[row][col] == '1' ||
mat[row][col] == 's' ||
mat[row][col] == 'd') &&
!visited[row][col])
{
// Mark the adjacent cells as visited
visited[row][col] = true;
// Enqueue the adjacent cells
Node adjCell = new Node(
new Point(row, col), curr.dist + 1);
q.addLast(adjCell);
// Update the distance
// of the adjacent cells
d[row][col] = curr.dist + 1;
}
}
}
// If the destination
// is not reachable
if (!ok)
System.out.println(-1);
}
// Driver Code
public static void main(String[] args)
{
char mat[][] = { { '0', '1', '0', '1' },
{ '1', '0', '1', '1' },
{ '0', '1', '1', '1' },
{ '1', '1', '1', '0' } };
ROW = mat.length;
COL = mat[0].length;
Point src = new Point(0, 3);
Point dest = new Point(3, 0);
pathMoves(mat, src, dest);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach from collections import deque # Stores the coordinates # of the matrix cell class Point: def __init__(self, xx, yy): self.x = xx self.y = yy # Stores coordinates of # a cell and its distance class Node: def __init__(self, P, d): self.pt = P self.dist = d # Check if the given cell is valid or not def isValid(row, col): return (row >= 0) and (col >= 0) and (row < 4) and (col < 4) # Stores the moves of the directions of adjacent cells dRow = [-1, 0, 0, 1] dCol = [0, -1, 1, 0] # Function to find the shortest path from the # source to destination in the given matrix def pathMoves(mat, src, dest): # Stores the distance for each # cell from the source cell d = [[ -1 for i in range(4)] for i in range(4)] # Distance of source cell is 0 d[src.x][src.y] = 0 # Initialize a visited array visited = [[ False for i in range(4)] for i in range(4)] # memset(visited, false, sizeof visited) # Mark source cell as visited visited[src.x][src.y] = True # Create a queue for BFS q = deque() # Distance of source cell is 0 s = Node(src, 0) # Enqueue source cell q.append(s) # Keeps track of whether # destination is reached or not ok = False # Iterate until queue is not empty while (len(q)>0): # Deque front of the queue curr = q.popleft() pt = curr.pt # If the destination cell is # reached, then find the path if (pt.x == dest.x and pt.y == dest.y): xx, yy = pt.x, pt.y dist = curr.dist # Assign the distance of # destination to the # distance matrix d[pt.x][pt.y] = dist # Stores the smallest path pathmoves = "" # Iterate until source is reached while (xx != src.x or yy != src.y): # Append D if (xx > 0 and d[xx - 1][yy] == dist - 1): pathmoves += 'D' xx -= 1 # Append U if (xx < 4 - 1 and d[xx + 1][yy] == dist - 1): pathmoves += 'U' xx += 1 # Append R if (yy > 0 and d[xx][yy - 1] == dist - 1): pathmoves += 'R' yy -= 1 # Append L if (yy < 4 - 1 and d[xx][yy + 1] == dist - 1): pathmoves += 'L' yy += 1 dist -= 1 # Reverse the backtracked path pathmoves = pathmoves[::-1] print(pathmoves, end = "") ok = True break # Pop the start of queue # q.pop() # Explore all adjacent directions for i in range(4): row = pt.x + dRow[i] col = pt.y + dCol[i] # If the current cell is valid # cell and can be traversed if (isValid(row, col) and (mat[row][col] == '1' or mat[row][col] == 's' or mat[row][col] == 'd') and (not visited[row][col])): # Mark the adjacent cells as visited visited[row][col] = True # Enqueue the adjacent cells adjCell = Node( Point(row, col), curr.dist + 1) q.append(adjCell) # Update the distance # of the adjacent cells d[row][col] = curr.dist + 1 # If the destination # is not reachable if (not ok): print(-1) # Driver Code if __name__ == '__main__': mat =[ ['0', '1', '0', '1'], [ '1', '0', '1', '1'], [ '0', '1', '1', '1'], [ '1', '1', '1', '0']] src = Point(0, 3) dest = Point(3, 0) pathMoves(mat, src, dest) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int ROW;
static int COL;
// Stores the coordinates
// of the matrix cell
class Point
{
public int x, y;
};
static Point newPoint(int x, int y)
{
Point temp = new Point();
temp.x = x;
temp.y = y;
return temp;
}
// Stores coordinates of
// a cell and its distance
class Node
{
public Point pt;
public int dist;
};
static Node newNode(Point p, int dist)
{
Node temp = new Node();
temp.pt = p;
temp.dist = dist;
return temp;
}
// Check if the given cell is valid or not
static bool isValid(int row, int col)
{
return (row >= 0) && (col >= 0) &&
(row < ROW) && (col < COL);
}
// Stores the moves of the directions
// of adjacent cells
static int []dRow = { -1, 0, 0, 1 };
static int []dCol = { 0, -1, 1, 0 };
// Function to find the shortest path from the
// source to destination in the given matrix
static void pathMoves(char [,]mat, Point src,
Point dest)
{
// Stores the distance for each
// cell from the source cell
int [,]d = new int[ROW, COL];
for(int i = 0; i < ROW; i++)
{
for(int j = 0; j < COL; j++)
d[i, j] = -1;
}
// Distance of source cell is 0
d[src.x, src.y] = 0;
// Initialize a visited array
bool [,]visited = new bool[ROW, COL];
// Mark source cell as visited
visited[src.x, src.y] = true;
// Create a queue for BFS
Queue<Node> q = new Queue<Node>();
// Distance of source cell is 0
Node s = newNode(src, 0);
// Enqueue source cell
q.Enqueue(s);
// Keeps track of whether
// destination is reached or not
bool ok = false;
// Iterate until queue is not empty
while (q.Count > 0)
{
// Deque front of the queue
Node curr = q.Peek();
q.Dequeue();
Point pt = curr.pt;
// If the destination cell is
// reached, then find the path
if (pt.x == dest.x && pt.y == dest.y)
{
int xx = pt.x, yy = pt.y;
int dist = curr.dist;
// Assign the distance of
// destination to the
// distance matrix
d[pt.x,pt.y] = dist;
// Stores the smallest path
string pathmoves = "";
// Iterate until source is reached
while (xx != src.x || yy != src.y)
{
// Append D
if (xx > 0 &&
d[xx - 1, yy] == dist - 1)
{
pathmoves += 'D';
xx--;
}
// Append U
if (xx < ROW - 1 &&
d[xx + 1, yy] == dist - 1)
{
pathmoves += 'U';
xx++;
}
// Append R
if (yy > 0 &&
d[xx, yy - 1] == dist - 1)
{
pathmoves += 'R';
yy--;
}
// Append L
if (yy < COL - 1 &&
d[xx, yy + 1] == dist - 1)
{
pathmoves += 'L';
yy++;
}
dist--;
}
// Print reverse the backtracked path
for(int i = pathmoves.Length - 1;
i >= 0; --i)
Console.Write(pathmoves[i]);
ok = true;
break;
}
// Pop the start of queue
if (q.Count > 0)
{
q.Peek();
q.Dequeue();
}
// Explore all adjacent directions
for(int i = 0; i < 4; i++)
{
int row = pt.x + dRow[i];
int col = pt.y + dCol[i];
// If the current cell is valid
// cell and can be traversed
if (isValid(row, col) &&
(mat[row, col] == '1' ||
mat[row, col] == 's' ||
mat[row, col] == 'd') &&
!visited[row, col])
{
// Mark the adjacent cells as visited
visited[row,col] = true;
// Enqueue the adjacent cells
Node adjCell = newNode(newPoint(row, col),
curr.dist + 1);
q.Enqueue(adjCell);
// Update the distance
// of the adjacent cells
d[row, col] = curr.dist + 1;
}
}
}
// If the destination
// is not reachable
if (ok == false)
Console.Write(-1);
}
// Driver Code
public static void Main()
{
char [,]mat = { { '0', '1', '0', '1' },
{ '1', '0', '1', '1' },
{ '0', '1', '1', '1' },
{ '1', '1', '1', '0' } };
ROW = mat.GetLength(0);
COL = mat.GetLength(0);
Point src = newPoint(0, 3);
Point dest = newPoint(3, 0);
pathMoves(mat, src, dest);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
var ROW = 0;
var COL = 0;
// Stores the coordinates
// of the matrix cell
class Point
{
constructor()
{
this.x = 0;
this.y = 0;
}
};
function newPoint(x, y)
{
var temp = new Point();
temp.x = x;
temp.y = y;
return temp;
}
// Stores coordinates of
// a cell and its distance
class Node
{
constructor()
{
this.pt = null;
this.dist = 0;
}
};
function newNode(p, dist)
{
var temp = new Node();
temp.pt = p;
temp.dist = dist;
return temp;
}
// Check if the given cell is valid or not
function isValid(row, col)
{
return (row >= 0) && (col >= 0) &&
(row < ROW) && (col < COL);
}
// Stores the moves of the directions
// of adjacent cells
var dRow = [-1, 0, 0, 1];
var dCol = [0, -1, 1, 0];
// Function to find the shortest path from the
// source to destination in the given matrix
function pathMoves(mat, src, dest)
{
// Stores the distance for each
// cell from the source cell
var d = Array.from(Array(ROW), ()=>Array(COL));
for(var i = 0; i < ROW; i++)
{
for(var j = 0; j < COL; j++)
d[i][j] = -1;
}
// Distance of source cell is 0
d[src.x][src.y] = 0;
// Initialize a visited array
var visited = Array.from(Array(ROW), ()=>Array(COL));
// Mark source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
var q = [];
// Distance of source cell is 0
var s = newNode(src, 0);
// push source cell
q.push(s);
// Keeps track of whether
// destination is reached or not
var ok = false;
// Iterate until queue is not empty
while (q.length > 0)
{
// Deque front of the queue
var curr = q[0];
q.shift();
var pt = curr.pt;
// If the destination cell is
// reached, then find the path
if (pt.x == dest.x && pt.y == dest.y)
{
var xx = pt.x, yy = pt.y;
var dist = curr.dist;
// Assign the distance of
// destination to the
// distance matrix
d[pt.x][pt.y] = dist;
// Stores the smallest path
var pathmoves = "";
// Iterate until source is reached
while (xx != src.x || yy != src.y)
{
// Append D
if (xx > 0 &&
d[xx - 1][yy] == dist - 1)
{
pathmoves += 'D';
xx--;
}
// Append U
if (xx < ROW - 1 &&
d[xx + 1][yy] == dist - 1)
{
pathmoves += 'U';
xx++;
}
// Append R
if (yy > 0 &&
d[xx][yy - 1] == dist - 1)
{
pathmoves += 'R';
yy--;
}
// Append L
if (yy < COL - 1 &&
d[xx][yy + 1] == dist - 1)
{
pathmoves += 'L';
yy++;
}
dist--;
}
// Print reverse the backtracked path
for(var i = pathmoves.length - 1;
i >= 0; --i)
document.write(pathmoves[i]);
ok = true;
break;
}
// Pop the start of queue
if (q.length > 0)
{
q.shift();
}
// Explore all adjacent directions
for(var i = 0; i < 4; i++)
{
var row = pt.x + dRow[i];
var col = pt.y + dCol[i];
// If the current cell is valid
// cell and can be traversed
if (isValid(row, col) &&
(mat[row][col] == '1' ||
mat[row][col] == 's' ||
mat[row][col] == 'd') &&
!visited[row][col])
{
// Mark the adjacent cells as visited
visited[row][col] = true;
// Enqueue the adjacent cells
var adjCell = newNode(newPoint(row, col),
curr.dist + 1);
q.push(adjCell);
// Update the distance
// of the adjacent cells
d[row][col] = curr.dist + 1;
}
}
}
// If the destination
// is not reachable
if (ok == false)
document.write(-1);
}
// Driver Code
var mat = [ [ '0', '1', '0', '1' ],
[ '1', '0', '1', '1' ],
[ '0', '1', '1', '1' ],
[ '1', '1', '1', '0' ] ];
ROW = mat.length;
COL = mat[0].length;
var src = newPoint(0, 3);
var dest = newPoint(3, 0);
pathMoves(mat, src, dest);
// This code is contributed by rutvik_56.
</script>
Producción:
DLDLDL
Complejidad de tiempo: O (N * M), ya que estamos usando bucles anidados para atravesar la array.
Espacio auxiliar: O(N*M), ya que estamos usando espacio adicional para la array visitada.
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA