Considere una rata colocada en (0, 0) en una array cuadrada m[ ][ ] de orden n y tiene que llegar al destino en (n-1, n-1) . La tarea es encontrar una array ordenada de strings que indiquen todas las direcciones posibles que la rata puede tomar para llegar al destino en (n-1, n-1) . Las direcciones en las que la rata puede moverse son ‘U’ (arriba), ‘D’ (abajo), ‘L’ (izquierda), ‘R’ (derecha).
Ejemplos:
Entrada: N = 4
1 0 0 0
1 1 0 1
0 1 0 0
0 1 1 1
Salida:
DRDDRR
Entrada: N = 4
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
Salida:
DDRDRR DRDDRR
Explicación:
Solución:
Enfoque de fuerza bruta:
Podemos usar el retroceso simple sin usar ningún espacio adicional.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define MAX 5
using namespace std;
void getallpath(int matrix[MAX][MAX], int n,int row,int col,vector<string> &ans,string cur)
{
if(row>=n or col>=n or row<0 or col<0 or matrix[row][col] == 0)
return ;
if(row == n-1 and col == n-1)
{
ans.push_back(cur);
return ;
}
//now if its one we have 4 calls
matrix[row][col] = 0;
getallpath(matrix,n,row-1,col,ans,cur+"U");
getallpath(matrix,n,row,col+1,ans,cur+"R");
getallpath(matrix,n,row,col-1,ans,cur+"L");
getallpath(matrix,n,row+1,col,ans,cur+"D");
matrix[row][col] = 1;
return ;
}
vector<string> findPath(int matrix[MAX][MAX], int n) {
// Your code goes here
vector<string> ans;
getallpath(matrix,n,0,0,ans,"");
return ans;
}
int main()
{
int m[MAX][MAX] = { { 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1 } };
int n = sizeof(m) / sizeof(m[0]);
vector<string> ans = findPath(m, n);
for(auto i : ans)
cout<<i<<" ";
return 0;
}
Producción
DRRRRDDD DRDRURRDDD DDRURRRDDD DDRRURRDDD
Análisis de Complejidad:
Complejidad del tiempo : O(4^(n^2)).
Como estamos haciendo 4 llamadas para cada celda de la array.
Espacio Auxiliar: O(1).
Como no estamos usando ningún espacio extra.
Enfoque 2:
- Comience desde el índice inicial (es decir, (0,0)) y busque los movimientos válidos a través de las celdas adyacentes en el orden Abajo->Izquierda->Derecha->Arriba (para obtener las rutas ordenadas) en la cuadrícula.
- Si el movimiento es posible, muévase a esa celda mientras almacena el carácter correspondiente al movimiento (D, L, R, U) y nuevamente comience a buscar el movimiento válido hasta el último índice (es decir, (n-1, n-1 )) es alcanzado.
- Además, siga marcando las celdas como visitadas y cuando hayamos recorrido todos los caminos posibles desde esa celda, luego desmarque esa celda para otros caminos diferentes y elimine el carácter del camino formado.
- Cuando se alcance el último índice de la cuadrícula (abajo a la derecha), almacene la ruta recorrida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define MAX 5
using namespace std;
// Function returns true if the
// move taken is valid else
// it will return false.
bool isSafe(int row, int col, int m[][MAX],
int n, bool visited[][MAX])
{
if (row == -1 || row == n || col == -1 ||
col == n || visited[row][col]
|| m[row][col] == 0)
return false;
return true;
}
// Function to print all the possible
// paths from (0, 0) to (n-1, n-1).
void printPathUtil(int row, int col, int m[][MAX],
int n, string& path, vector<string>&
possiblePaths, bool visited[][MAX])
{
// This will check the initial point
// (i.e. (0, 0)) to start the paths.
if (row == -1 || row == n || col == -1
|| col == n || visited[row][col]
|| m[row][col] == 0)
return;
// If reach the last cell (n-1, n-1)
// then store the path and return
if (row == n - 1 && col == n - 1) {
possiblePaths.push_back(path);
return;
}
// Mark the cell as visited
visited[row][col] = true;
// Try for all the 4 directions (down, left,
// right, up) in the given order to get the
// paths in lexicographical order
// Check if downward move is valid
if (isSafe(row + 1, col, m, n, visited))
{
path.push_back('D');
printPathUtil(row + 1, col, m, n,
path, possiblePaths, visited);
path.pop_back();
}
// Check if the left move is valid
if (isSafe(row, col - 1, m, n, visited))
{
path.push_back('L');
printPathUtil(row, col - 1, m, n,
path, possiblePaths, visited);
path.pop_back();
}
// Check if the right move is valid
if (isSafe(row, col + 1, m, n, visited))
{
path.push_back('R');
printPathUtil(row, col + 1, m, n,
path, possiblePaths, visited);
path.pop_back();
}
// Check if the upper move is valid
if (isSafe(row - 1, col, m, n, visited))
{
path.push_back('U');
printPathUtil(row - 1, col, m, n,
path, possiblePaths, visited);
path.pop_back();
}
// Mark the cell as unvisited for
// other possible paths
visited[row][col] = false;
}
// Function to store and print
// all the valid paths
void printPath(int m[MAX][MAX], int n)
{
// vector to store all the possible paths
vector<string> possiblePaths;
string path;
bool visited[n][MAX];
memset(visited, false, sizeof(visited));
// Call the utility function to
// find the valid paths
printPathUtil(0, 0, m, n, path,
possiblePaths, visited);
// Print all possible paths
for (int i = 0; i < possiblePaths.size(); i++)
cout << possiblePaths[i] << " ";
}
// Driver code
int main()
{
int m[MAX][MAX] = { { 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1 } };
int n = sizeof(m) / sizeof(m[0]);
printPath(m, n);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// Vector to store all the possible paths
static Vector<String> possiblePaths = new Vector<>();
static String path = "";
static final int MAX = 5;
// Function returns true if the
// move taken is valid else
// it will return false.
static boolean isSafe(int row, int col, int m[][],
int n, boolean visited[][])
{
if (row == -1 || row == n || col == -1 ||
col == n || visited[row][col] ||
m[row][col] == 0)
return false;
return true;
}
// Function to print all the possible
// paths from (0, 0) to (n-1, n-1).
static void printPathUtil(int row, int col, int m[][],
int n, boolean visited[][])
{
// This will check the initial point
// (i.e. (0, 0)) to start the paths.
if (row == -1 || row == n || col == -1 ||
col == n || visited[row][col] ||
m[row][col] == 0)
return;
// If reach the last cell (n-1, n-1)
// then store the path and return
if (row == n - 1 && col == n - 1)
{
possiblePaths.add(path);
return;
}
// Mark the cell as visited
visited[row][col] = true;
// Try for all the 4 directions (down, left,
// right, up) in the given order to get the
// paths in lexicographical order
// Check if downward move is valid
if (isSafe(row + 1, col, m, n, visited))
{
path += 'D';
printPathUtil(row + 1, col, m, n,
visited);
path = path.substring(0, path.length() - 1);
}
// Check if the left move is valid
if (isSafe(row, col - 1, m, n, visited))
{
path += 'L';
printPathUtil(row, col - 1, m, n,
visited);
path = path.substring(0, path.length() - 1);
}
// Check if the right move is valid
if (isSafe(row, col + 1, m, n, visited))
{
path += 'R';
printPathUtil(row, col + 1, m, n,
visited);
path = path.substring(0, path.length() - 1);
}
// Check if the upper move is valid
if (isSafe(row - 1, col, m, n, visited))
{
path += 'U';
printPathUtil(row - 1, col, m, n,
visited);
path = path.substring(0, path.length() - 1);
}
// Mark the cell as unvisited for
// other possible paths
visited[row][col] = false;
}
// Function to store and print
// all the valid paths
static void printPath(int m[][], int n)
{
boolean [][]visited = new boolean[n][MAX];
// Call the utility function to
// find the valid paths
printPathUtil(0, 0, m, n, visited);
// Print all possible paths
for(int i = 0; i < possiblePaths.size(); i++)
System.out.print(possiblePaths.get(i) + " ");
}
// Driver code
public static void main(String[] args)
{
int m[][] = { { 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1 } };
int n = m.length;
printPath(m, n);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation of the above approach from typing import List MAX = 5 # Function returns true if the # move taken is valid else # it will return false. def isSafe(row: int, col: int, m: List[List[int]], n: int, visited: List[List[bool]]) -> bool: if (row == -1 or row == n or col == -1 or col == n or visited[row][col] or m[row][col] == 0): return False return True # Function to print all the possible # paths from (0, 0) to (n-1, n-1). def printPathUtil(row: int, col: int, m: List[List[int]], n: int, path: str, possiblePaths: List[str], visited: List[List[bool]]) -> None: # This will check the initial point # (i.e. (0, 0)) to start the paths. if (row == -1 or row == n or col == -1 or col == n or visited[row][col] or m[row][col] == 0): return # If reach the last cell (n-1, n-1) # then store the path and return if (row == n - 1 and col == n - 1): possiblePaths.append(path) return # Mark the cell as visited visited[row][col] = True # Try for all the 4 directions (down, left, # right, up) in the given order to get the # paths in lexicographical order # Check if downward move is valid if (isSafe(row + 1, col, m, n, visited)): path += 'D' printPathUtil(row + 1, col, m, n, path, possiblePaths, visited) path = path[:-1] # Check if the left move is valid if (isSafe(row, col - 1, m, n, visited)): path += 'L' printPathUtil(row, col - 1, m, n, path, possiblePaths, visited) path = path[:-1] # Check if the right move is valid if (isSafe(row, col + 1, m, n, visited)): path += 'R' printPathUtil(row, col + 1, m, n, path, possiblePaths, visited) path = path[:-1] # Check if the upper move is valid if (isSafe(row - 1, col, m, n, visited)): path += 'U' printPathUtil(row - 1, col, m, n, path, possiblePaths, visited) path = path[:-1] # Mark the cell as unvisited for # other possible paths visited[row][col] = False # Function to store and print # all the valid paths def printPath(m: List[List[int]], n: int) -> None: # vector to store all the possible paths possiblePaths = [] path = "" visited = [[False for _ in range(MAX)] for _ in range(n)] # Call the utility function to # find the valid paths printPathUtil(0, 0, m, n, path, possiblePaths, visited) # Print all possible paths for i in range(len(possiblePaths)): print(possiblePaths[i], end = " ") # Driver code if __name__ == "__main__": m = [ [ 1, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 0, 1 ], [ 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 1 ] ] n = len(m) printPath(m, n) # This code is contributed by sanjeev2552
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG{
// List to store all the possible paths
static List<String> possiblePaths = new List<String>();
static String path = "";
static readonly int MAX = 5;
// Function returns true if the
// move taken is valid else
// it will return false.
static bool isSafe(int row, int col, int [,]m,
int n, bool [,]visited)
{
if (row == -1 || row == n || col == -1 ||
col == n || visited[row,col] ||
m[row,col] == 0)
return false;
return true;
}
// Function to print all the possible
// paths from (0, 0) to (n-1, n-1).
static void printPathUtil(int row, int col, int [,]m,
int n, bool [,]visited)
{
// This will check the initial point
// (i.e. (0, 0)) to start the paths.
if (row == -1 || row == n || col == -1 ||
col == n || visited[row,col] ||
m[row,col] == 0)
return;
// If reach the last cell (n-1, n-1)
// then store the path and return
if (row == n - 1 && col == n - 1)
{
possiblePaths.Add(path);
return;
}
// Mark the cell as visited
visited[row,col] = true;
// Try for all the 4 directions (down, left,
// right, up) in the given order to get the
// paths in lexicographical order
// Check if downward move is valid
if (isSafe(row + 1, col, m, n, visited))
{
path += 'D';
printPathUtil(row + 1, col, m, n,
visited);
path = path.Substring(0, path.Length - 1);
}
// Check if the left move is valid
if (isSafe(row, col - 1, m, n, visited))
{
path += 'L';
printPathUtil(row, col - 1, m, n,
visited);
path = path.Substring(0, path.Length - 1);
}
// Check if the right move is valid
if (isSafe(row, col + 1, m, n, visited))
{
path += 'R';
printPathUtil(row, col + 1, m, n,
visited);
path = path.Substring(0, path.Length - 1);
}
// Check if the upper move is valid
if (isSafe(row - 1, col, m, n, visited))
{
path += 'U';
printPathUtil(row - 1, col, m, n,
visited);
path = path.Substring(0, path.Length - 1);
}
// Mark the cell as unvisited for
// other possible paths
visited[row,col] = false;
}
// Function to store and print
// all the valid paths
static void printPath(int [,]m, int n)
{
bool [,]visited = new bool[n,MAX];
// Call the utility function to
// find the valid paths
printPathUtil(0, 0, m, n, visited);
// Print all possible paths
for(int i = 0; i < possiblePaths.Count; i++)
Console.Write(possiblePaths[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
int [,]m = { { 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1 } };
int n = m.GetLength(0);
printPath(m, n);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript implementation of the above approach
// Vector to store all the possible paths
let possiblePaths = [];
let path = "";
let MAX = 5;
// Function returns true if the
// move taken is valid else
// it will return false.
function isSafe(row, col, m, n, visited)
{
if (row == -1 || row == n || col == -1 ||
col == n || visited[row][col] ||
m[row][col] == 0)
return false;
return true;
}
// Function to print all the possible
// paths from (0, 0) to (n-1, n-1).
function printPathUtil(row, col, m, n, visited)
{
// This will check the initial point
// (i.e. (0, 0)) to start the paths.
if (row == -1 || row == n || col == -1 ||
col == n || visited[row][col] ||
m[row][col] == 0)
return;
// If reach the last cell (n-1, n-1)
// then store the path and return
if (row == n - 1 && col == n - 1)
{
possiblePaths.push(path);
return;
}
// Mark the cell as visited
visited[row][col] = true;
// Try for all the 4 directions (down, left,
// right, up) in the given order to get the
// paths in lexicographical order
// Check if downward move is valid
if (isSafe(row + 1, col, m, n, visited))
{
path += 'D';
printPathUtil(row + 1, col, m, n,
visited);
path = path.substring(0, path.length - 1);
}
// Check if the left move is valid
if (isSafe(row, col - 1, m, n, visited))
{
path += 'L';
printPathUtil(row, col - 1, m, n,
visited);
path = path.substring(0, path.length - 1);
}
// Check if the right move is valid
if (isSafe(row, col + 1, m, n, visited))
{
path += 'R';
printPathUtil(row, col + 1, m, n,
visited);
path = path.substring(0, path.length - 1);
}
// Check if the upper move is valid
if (isSafe(row - 1, col, m, n, visited))
{
path += 'U';
printPathUtil(row - 1, col, m, n,
visited);
path = path.substring(0, path.length - 1);
}
// Mark the cell as unvisited for
// other possible paths
visited[row][col] = false;
}
// Function to store and print
// all the valid paths
function printPath(m, n)
{
let visited = new Array(n);
for(let i = 0; i < n; i++)
{
visited[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
visited[i][j] = false;
}
// Call the utility function to
// find the valid paths
printPathUtil(0, 0, m, n, visited);
// Print all possible paths
for(let i = 0; i < possiblePaths.length; i++)
document.write(possiblePaths[i] + " ");
}
// Driver code
let m = [ [ 1, 0, 0, 0, 0 ],
[ 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 0, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ] ];
let n = m.length;
printPath(m, n);
// This code is contributed by patel2127
</script>
Producción
DDRRURRDDD DDRURRRDDD DRDRURRDDD DRRRRDDD
Análisis de Complejidad:
- Complejidad del tiempo : O(3^(n^2)).
Como hay N ^ 2 celdas de cada celda, hay 3 celdas vecinas no visitadas. Entonces la complejidad del tiempo O(3^(N^2). - Espacio auxiliar: O(3^(n^2)).
Como puede haber como máximo 3^(n^2) celdas en la respuesta, la complejidad del espacio es O(3^(n^2)).
Enfoque eficiente:
En lugar de mantener la array visitada, podemos modificar la array dada para tratarla como array visitada.
A continuación se muestra la implementación:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define MAX 5
using namespace std;
vector<string> res;
bool isValid(int row, int col, int m[][MAX], int n)
{
if (row >= 0 && row < n && col >= 0 && col < n
&& m[row][col] == 1) {
return true;
}
return false;
}
void findPathHelper(int m[][MAX], int n, int x, int y,
int dx[], int dy[], string path)
{
if (x == n - 1 && y == n - 1) {
res.push_back(path);
return;
}
string dir = "DLRU";
for (int i = 0; i < 4; i++) {
int row = x + dx[i];
int col = y + dy[i];
if (isValid(row, col, m, n)) {
m[row][col] = 2; // used to track visited cells
// of matrix
findPathHelper(m, n, row, col, dx, dy,
path + dir[i]);
m[row][col]
= 1; // mark it unvisited yet explorable
}
}
}
vector<string> findPath(int m[][MAX], int n)
{
// dx, dy will be used to follow `DLRU` exploring
// approach which is lexicographically sorted order
int dx[] = { 1, 0, 0, -1 };
int dy[] = { 0, -1, 1, 0 };
if (m[0][0] == 1) {
m[0][0] = 2;
findPathHelper(m, n, 0, 0, dx, dy, "");
}
return res;
}
int main()
{
int m[MAX][MAX] = { { 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1 } };
int n = sizeof(m) / sizeof(m[0]);
findPath(m, n);
for (int i = 0; i < res.size(); ++i)
cout << res[i] << ' ';
return 0;
}
// This code is contributed by jainlovely450
Java
import java.io.*;
import java.util.*;
class GFG {
static ArrayList<String> res;
public static ArrayList<String> findPath(int[][] m, int n) {
res = new ArrayList<>();
// dx, dy will be used to follow `DLRU` exploring approach
// which is lexicographically sorted order
int[] dx = { 1, 0, 0, -1 };
int[] dy = { 0, -1, 1, 0 };
if (m[0][0] == 1) {
m[0][0] = 2;
findPathHelper(m, n, 0, 0, dx, dy, "");
}
return res;
}
private static void findPathHelper(int[][] m, int n, int x, int y, int[] dx, int[] dy, String path) {
if (x == n - 1 && y == n - 1) {
res.add(path);
return;
}
String dir = "DLRU";
for (int i = 0; i < 4; i++) {
int row = x + dx[i];
int col = y + dy[i];
if (isValid(row, col, m, n)) {
m[row][col] = 2; // used to track visited cells of matrix
findPathHelper(m, n, row, col, dx, dy, path + dir.charAt(i));
m[row][col] = 1; // mark it unvisited yet explorable
}
}
}
private static boolean isValid(int row, int col, int[][] m, int n) {
if (row >= 0 && row < n && col >= 0 && col < n && m[row][col] == 1) {
return true;
}
return false;
}
public static void main(String[] args) {
int m[][] = { { 1, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 1 } };
int n = m.length;
ArrayList<String> ans = findPath(m, n);
System.out.println(ans);
}
}
// Contributed by: jmamtora99
Python3
# Python code for the approach res = [] def isValid(row, col, m, n): if (row >= 0 and row < n and col >= 0 and col < n and m[row][col] == 1): return True return False def findPathHelper(m, n, x, y, dx, dy, path): global res if (x == n - 1 and y == n - 1): res.append(path) return dir = "DLRU" for i in range(4): row = x + dx[i] col = y + dy[i] if (isValid(row, col, m, n)): m[row][col] = 2 # used to track visited cells of matrix findPathHelper(m, n, row, col, dx, dy, path + dir[i]) m[row][col] = 1 # mark it unvisited yet explorable def findPath(m,n): global res res.clear() # dx, dy will be used to follow `DLRU` exploring approach # which is lexicographically sorted order dx = [ 1, 0, 0, -1 ] dy = [ 0, -1, 1, 0 ] if (m[0][0] == 1): m[0][0] = 2 findPathHelper(m, n, 0, 0, dx, dy, "") return res # driver code m = [ [ 1, 0, 0, 0, 0 ], [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 0, 1 ], [ 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 1 ] ] n = len(m) ans = findPath(m, n) print(ans) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript implementation of the above approach
const MAX = 5;
let res = [];
function isValid(row, col, m, n)
{
if (row >= 0 && row < n && col >= 0 && col < n
&& m[row][col] == 1) {
return true;
}
return false;
}
function findPathHelper(m, n, x, y, dx, dy, path)
{
if (x == n - 1 && y == n - 1) {
res.push(path);
return;
}
let dir = "DLRU";
for (let i = 0; i < 4; i++) {
let row = x + dx[i];
let col = y + dy[i];
if (isValid(row, col, m, n)) {
m[row][col] = 2; // used to track visited cells
// of matrix
findPathHelper(m, n, row, col, dx, dy,
path + dir[i]);
m[row][col] = 1; // mark it unvisited yet explorable
}
}
}
function findPath(m, n)
{
// dx, dy will be used to follow `DLRU` exploring
// approach which is lexicographically sorted order
let dx = [ 1, 0, 0, -1 ];
let dy = [ 0, -1, 1, 0 ];
if (m[0][0] == 1) {
m[0][0] = 2;
findPathHelper(m, n, 0, 0, dx, dy, "");
}
return res;
}
// driver code
let m = [ [ 1, 0, 0, 0, 0 ],
[ 1, 1, 1, 1, 1 ],
[ 1, 1, 1, 0, 1 ],
[ 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 1 ] ];
let n = m.length;
findPath(m, n);
for (let i = 0; i < res.length; ++i)
document.write(res[i],' ');
// This code is contributed by shinjanpatra
</script>
Producción
DDRRURRDDD DDRURRRDDD DRDRURRDDD DRRRRDDD
Análisis de Complejidad:
- Complejidad de tiempo: O(3^(n^2)).
- Complejidad espacial: O(1); Dado que no estamos utilizando la array visitada.
Publicación traducida automáticamente
Artículo escrito por Rishav Saxena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA