Dada una array N x M. Cada celda de la array tiene un valor numérico que apunta a la siguiente celda a la que conduce. Los valores de array[i][j] pueden ser:
- 1 que significa ir a la celda de la derecha . (es decir, pasar de array[i][j] a array[i][j + 1])
- 2 que significa ir a la celda de la izquierda . (es decir, pasar de array[i][j] a array[i][j – 1])
- 3 que significa ir a la celda inferior . (es decir, pasar de array[i][j] a array[i + 1][j])
- 4 que significa ir a la celda superior . (es decir, pasar de array[i][j] a array[i – 1][j])
Se dan la celda de origen (x1, y1) y la celda de destino (x2, y2). La tarea es encontrar si existe una ruta entre la celda de origen dada y la celda de destino.
Ejemplos :
Entrada : array[][] = {{3, 2, 2, 2}, {3, 4, 2, 3}, {1, 3, 4, 4}, {2, 1, 1, 2}, { 4, 4, 3, 3}}, celda de origen = {0, 3}, celda de destino = {3, 1}
Salida : Sí
3 2 2 2 3 4 2 3 1 3 4 4 2 1 1 2 4 4 3 3 Explicación : a partir de la celda (0, 3), siga la ruta según la regla de dirección. Recorra las celdas en el siguiente orden: (0, 3)->(0, 2)->(0, 1)->(0, 0)->(1, 0)->(2, 0)-> (2, 1)->(3, 1) que es el destino.
Entrada : array[][]={{1, 4, 3}, {2, 3, 2}, {4, 1, 4}}, celda de origen = {1, 1}, celda de destino = {0, 3 }
Salida : No
1 4 3 2 3 2 4 1 4 Explicación : a partir de la celda (1, 1), siga la ruta según la regla de dirección. Atraviese las celdas como: (1, 1)->(2, 1)->(2, 2)->(1, 2)->(1, 1), aquí se vuelve a visitar la celda de origen y, por lo tanto, en cualquier caso la celda de destino no se visita.
Enfoque : la tarea se puede resolver utilizando DFS o BFS .
- Se puede observar que el camino a seguir es fijo y necesitamos recorrer la array en base a la regla de dirección asignada.
- Inicie DFS o BFS desde la celda de origen y muévase según la regla de dirección descrita anteriormente.
- Si se alcanza la celda de destino, se encuentra una ruta válida .
- Si una celda visitada se vuelve a visitar o los índices de la celda actual salen del rango , entonces no se llega a la celda de destino a través de esa ruta; de lo contrario, continúa.
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;
// Function to check whether a valid path
// exists or not
bool uniquepath(vector<vector<int> >& matrix, int curr_x,
int curr_y, int dest_x, int dest_y,
vector<vector<bool> >& visited)
{
// Check if destination cell is reached
if (curr_x == dest_x && curr_y == dest_y)
return true;
// Base Cases
if (!(curr_x >= 0 && curr_x < matrix.size()
&& curr_y >= 0 && curr_y < matrix[0].size()))
return false;
// Check whether a visited cell is
// re-visited again
if (visited[curr_x][curr_y] == true)
return false;
// Mark current cell as visited
visited[curr_x][curr_y] = true;
// Moving based on direction rule
if (matrix[curr_x][curr_y] == 1)
return uniquepath(matrix, curr_x, curr_y + 1,
dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 2)
return uniquepath(matrix, curr_x, curr_y - 1,
dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 3)
return uniquepath(matrix, curr_x + 1, curr_y,
dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 4)
return uniquepath(matrix, curr_x - 1, curr_y,
dest_x, dest_y, visited);
}
// Driver code
int main()
{
vector<vector<int> > matrix = { { 3, 2, 2, 2 },
{ 3, 4, 2, 3 },
{ 1, 3, 4, 4 },
{ 2, 1, 1, 2 },
{ 4, 4, 1, 2 } };
int start_x = 0, start_y = 3;
int dest_x = 3, dest_y = 1;
int n = matrix.size();
int m = matrix[0].size();
vector<vector<bool> > visited(
n,
vector<bool>(m, false));
if (uniquepath(matrix, start_x, start_y,
dest_x, dest_y,
visited))
cout << "Yes";
else
cout << "No";
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check whether a valid path
// exists or not
static boolean uniquepath(int[][]matrix, int curr_x,
int curr_y, int dest_x,
int dest_y, boolean[][] visited)
{
// Check if destination cell is reached
if (curr_x == dest_x && curr_y == dest_y)
return true;
// Base Cases
if (!(curr_x >= 0 && curr_x < matrix.length &&
curr_y >= 0 && curr_y < matrix[0].length))
return false;
// Check whether a visited cell is
// re-visited again
if (visited[curr_x][curr_y] == true)
return false;
// Mark current cell as visited
visited[curr_x][curr_y] = true;
// Moving based on direction rule
if (matrix[curr_x][curr_y] == 1)
return uniquepath(matrix, curr_x, curr_y + 1,
dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 2)
return uniquepath(matrix, curr_x, curr_y - 1,
dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 3)
return uniquepath(matrix, curr_x + 1, curr_y,
dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 4)
return uniquepath(matrix, curr_x - 1, curr_y,
dest_x, dest_y, visited);
return false;
}
// Driver code
public static void main(String[] args)
{
int[][] matrix = { { 3, 2, 2, 2 },
{ 3, 4, 2, 3 },
{ 1, 3, 4, 4 },
{ 2, 1, 1, 2 },
{ 4, 4, 1, 2 } };
int start_x = 0, start_y = 3;
int dest_x = 3, dest_y = 1;
int n = matrix.length;
int m = matrix[0].length;
boolean[][] visited = new boolean[n][m];
if (uniquepath(matrix, start_x, start_y,
dest_x, dest_y, visited))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by 29AjayKumar
Python3
# python program for the above approach
# Function to check whether a valid path
# exists or not
def uniquepath(matrix, curr_x, curr_y, dest_x, dest_y, visited):
# Check if destination cell is reached
if (curr_x == dest_x and curr_y == dest_y):
return True
# Base Cases
if (not(curr_x >= 0 and curr_x < len(matrix) and curr_y >= 0 and curr_y < len(matrix[0]))):
return False
# Check whether a visited cell is
# re-visited again
if (visited[curr_x][curr_y] == True):
return False
# Mark current cell as visited
visited[curr_x][curr_y] = True
# Moving based on direction rule
if (matrix[curr_x][curr_y] == 1):
return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited)
elif (matrix[curr_x][curr_y] == 2):
return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited)
elif (matrix[curr_x][curr_y] == 3):
return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited)
elif (matrix[curr_x][curr_y] == 4):
return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited)
# Driver code
if __name__ == "__main__":
matrix = [[3, 2, 2, 2],
[3, 4, 2, 3],
[1, 3, 4, 4],
[2, 1, 1, 2],
[4, 4, 1, 2]
]
start_x = 0
start_y = 3
dest_x = 3
dest_y = 1
n = len(matrix)
m = len(matrix[0])
visited = [[False for _ in range(m)] for _ in range(n)]
if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited)):
print("Yes")
else:
print("No")
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
public class GFG{
// Function to check whether a valid path
// exists or not
static bool uniquepath(int[,]matrix, int curr_x,
int curr_y, int dest_x,
int dest_y, bool[,] visited)
{
// Check if destination cell is reached
if (curr_x == dest_x && curr_y == dest_y)
return true;
// Base Cases
if (!(curr_x >= 0 && curr_x < matrix.GetLength(0) &&
curr_y >= 0 && curr_y < matrix.GetLength(1)))
return false;
// Check whether a visited cell is
// re-visited again
if (visited[curr_x,curr_y] == true)
return false;
// Mark current cell as visited
visited[curr_x,curr_y] = true;
// Moving based on direction rule
if (matrix[curr_x,curr_y] == 1)
return uniquepath(matrix, curr_x, curr_y + 1,
dest_x, dest_y, visited);
else if (matrix[curr_x,curr_y] == 2)
return uniquepath(matrix, curr_x, curr_y - 1,
dest_x, dest_y, visited);
else if (matrix[curr_x,curr_y] == 3)
return uniquepath(matrix, curr_x + 1, curr_y,
dest_x, dest_y, visited);
else if (matrix[curr_x,curr_y] == 4)
return uniquepath(matrix, curr_x - 1, curr_y,
dest_x, dest_y, visited);
return false;
}
// Driver code
public static void Main(String[] args)
{
int[,] matrix = { { 3, 2, 2, 2 },
{ 3, 4, 2, 3 },
{ 1, 3, 4, 4 },
{ 2, 1, 1, 2 },
{ 4, 4, 1, 2 } };
int start_x = 0, start_y = 3;
int dest_x = 3, dest_y = 1;
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
bool[,] visited = new bool[n,m];
if (uniquepath(matrix, start_x, start_y,
dest_x, dest_y, visited))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to check whether a valid path
// exists or not
function uniquepath(matrix, curr_x, curr_y, dest_x, dest_y, visited)
{
// Check if destination cell is reached
if (curr_x == dest_x && curr_y == dest_y) return true;
// Base Cases
if (
!(
curr_x >= 0 &&
curr_x < matrix.length &&
curr_y >= 0 &&
curr_y < matrix[0].length
)
)
return false;
// Check whether a visited cell is
// re-visited again
if (visited[curr_x][curr_y] == true) return false;
// Mark current cell as visited
visited[curr_x][curr_y] = true;
// Moving based on direction rule
if (matrix[curr_x][curr_y] == 1)
return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 2)
return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 3)
return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited);
else if (matrix[curr_x][curr_y] == 4)
return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited);
}
// Driver code
let matrix = [
[3, 2, 2, 2],
[3, 4, 2, 3],
[1, 3, 4, 4],
[2, 1, 1, 2],
[4, 4, 1, 2],
];
let start_x = 0,
start_y = 3;
let dest_x = 3,
dest_y = 1;
let n = matrix.length;
let m = matrix[0].length;
let visited = new Array(n).fill(0).map(() => new Array(m).fill(false));
if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited))
document.write("Yes");
else document.write("No");
// This code is contributed by gfgking.
</script>
Producción
Yes
Complejidad de Tiempo : O(n*m)
Espacio Auxiliar : O(n*m)
Publicación traducida automáticamente
Artículo escrito por sudarshanmehta13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA