El problema es imprimir todas las rutas posibles desde la parte superior izquierda hasta la parte inferior derecha de una array mXn con las restricciones de que desde cada celda puede moverse solo hacia la derecha o hacia abajo .
Ejemplos:
Input : 1 2 3
4 5 6
Output : 1 4 5 6
1 2 5 6
1 2 3 6
Input : 1 2
3 4
Output : 1 2 4
1 3 4
El algoritmo es un algoritmo recursivo simple, desde cada celda primero imprime todas las rutas yendo hacia abajo y luego imprime todas las rutas yendo a la derecha. Haga esto recursivamente para cada celda encontrada.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to Print all possible paths from
// top left to bottom right of a mXn matrix
#include<iostream>
using namespace std;
/* mat: Pointer to the starting of mXn matrix
i, j: Current position of the robot (For the first call use 0,0)
m, n: Dimensions of given the matrix
pi: Next index to be filed in path array
*path[0..pi-1]: The path traversed by robot till now (Array to hold the
path need to have space for at least m+n elements) */
void printAllPathsUtil(int *mat, int i, int j, int m, int n, int *path, int pi)
{
// Reached the bottom of the matrix so we are left with
// only option to move right
if (i == m - 1)
{
for (int k = j; k < n; k++)
path[pi + k - j] = *((mat + i*n) + k);
for (int l = 0; l < pi + n - j; l++)
cout << path[l] << " ";
cout << endl;
return;
}
// Reached the right corner of the matrix we are left with
// only the downward movement.
if (j == n - 1)
{
for (int k = i; k < m; k++)
path[pi + k - i] = *((mat + k*n) + j);
for (int l = 0; l < pi + m - i; l++)
cout << path[l] << " ";
cout << endl;
return;
}
// Add the current cell to the path being generated
path[pi] = *((mat + i*n) + j);
// Print all the paths that are possible after moving down
printAllPathsUtil(mat, i+1, j, m, n, path, pi + 1);
// Print all the paths that are possible after moving right
printAllPathsUtil(mat, i, j+1, m, n, path, pi + 1);
// Print all the paths that are possible after moving diagonal
// printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1);
}
// The main function that prints all paths from
// top left to bottom right in a matrix 'mat' of size mXn
void printAllPaths(int *mat, int m, int n)
{
int *path = new int[m+n];
printAllPathsUtil(mat, 0, 0, m, n, path, 0);
}
// Driver program to test above functions
int main()
{
int mat[2][3] = { {1, 2, 3}, {4, 5, 6} };
printAllPaths(*mat, 2, 3);
return 0;
}
Java
import java.util.*;
// Java program to Print all possible paths from
// top left to bottom right of a mXn matrix
public class MatrixTraversal
{
private static void printMatrix(int mat[][], int m, int n,
int i, int j, List<Integer> list)
{
//return if i or j crosses matrix size
if(i > m || j > n)
return;
list.add(mat[i][j]);
if(i == m && j == n){
System.out.println(list);
}
printMatrix(mat, m, n, i+1, j, list);
printMatrix(mat, m, n, i, j+1, list);
list.remove(list.size()-1);
}
// Driver code
public static void main(String[] args)
{
int m = 2;
int n = 3;
int mat[][] = { { 1, 2, 3 },
{ 4, 5, 6 } };
List<Integer> list = new ArrayList<>();
printMatrix(mat, m-1, n-1, 0, 0, list);
}
}
//This article is contributed by Harneet
Python3
# Python3 program to Print all possible paths from # top left to bottom right of a mXn matrix ''' /* mat: Pointer to the starting of mXn matrix i, j: Current position of the robot (For the first call use 0, 0) m, n: Dimensions of given the matrix pi: Next index to be filed in path array *path[0..pi-1]: The path traversed by robot till now (Array to hold the path need to have space for at least m+n elements) */ ''' def printAllPathsUtil(mat, i, j, m, n, path, pi): # Reached the bottom of the matrix # so we are left with only option to move right if (i == m - 1): for k in range(j, n): path[pi + k - j] = mat[i][k] for l in range(pi + n - j): print(path[l], end = " ") print() return # Reached the right corner of the matrix # we are left with only the downward movement. if (j == n - 1): for k in range(i, m): path[pi + k - i] = mat[k][j] for l in range(pi + m - i): print(path[l], end = " ") print() return # Add the current cell # to the path being generated path[pi] = mat[i][j] # Print all the paths # that are possible after moving down printAllPathsUtil(mat, i + 1, j, m, n, path, pi + 1) # Print all the paths # that are possible after moving right printAllPathsUtil(mat, i, j + 1, m, n, path, pi + 1) # Print all the paths # that are possible after moving diagonal # printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1); # The main function that prints all paths # from top left to bottom right # in a matrix 'mat' of size mXn def printAllPaths(mat, m, n): path = [0 for i in range(m + n)] printAllPathsUtil(mat, 0, 0, m, n, path, 0) # Driver Code mat = [[1, 2, 3], [4, 5, 6]] printAllPaths(mat, 2, 3) # This code is contributed by Mohit Kumar
C#
// C# program to Print all possible paths from
// top left to bottom right of a mXn matrix
using System;
public class MatrixTraversal
{
/* mat: Pointer to the starting of mXn matrix
i, j: Current position of the robot (For the first call use 0,0)
m, n: Dimensions of given the matrix
pi: Next index to be filed in path array
*path[0..pi-1]: The path traversed by robot till now (Array to hold the
path need to have space for at least m+n elements) */
private static void printMatrix(int [,]mat, int m, int n,
int i, int j, int []path, int idx)
{
path[idx] = mat[i,j];
// Reached the bottom of the matrix so we are left with
// only option to move right
if (i == m - 1)
{
for (int k = j + 1; k < n; k++)
{
path[idx + k - j] = mat[i,k];
}
for (int l = 0; l < idx + n - j; l++)
{
Console.Write(path[l] + " ");
}
Console.WriteLine();
return;
}
// Reached the right corner of the matrix we are left with
// only the downward movement.
if (j == n - 1)
{
for (int k = i + 1; k < m; k++)
{
path[idx + k - i] = mat[k,j];
}
for (int l = 0; l < idx + m - i; l++)
{
Console.Write(path[l] + " ");
}
Console.WriteLine();
return;
}
// Print all the paths that are possible after moving down
printMatrix(mat, m, n, i + 1, j, path, idx + 1);
// Print all the paths that are possible after moving right
printMatrix(mat, m, n, i, j + 1, path, idx + 1);
}
// Driver code
public static void Main(String[] args)
{
int m = 2;
int n = 3;
int [,]mat = { { 1, 2, 3 },
{ 4, 5, 6 } };
int maxLengthOfPath = m + n - 1;
printMatrix(mat, m, n, 0, 0, new int[maxLengthOfPath], 0);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to Print all possible paths from
// top left to bottom right of a mXn matrix
/* mat: Pointer to the starting of mXn matrix
i, j: Current position of the robot (For the first call use 0,0)
m, n: Dimensions of given the matrix
pi: Next index to be filed in path array
*path[0..pi-1]: The path traversed by robot till now (Array to hold the
path need to have space for at least m+n elements) */
function printMatrix(mat,m,n,i,j,path,idx)
{
path[idx] = mat[i][j];
// Reached the bottom of the matrix so we are left with
// only option to move right
if (i == m - 1)
{
for (let k = j + 1; k < n; k++)
{
path[idx + k - j] = mat[i][k];
}
for (let l = 0; l < idx + n - j; l++)
{
document.write(path[l] + " ");
}
document.write("<br>");
return;
}
// Reached the right corner of the matrix we are left with
// only the downward movement.
if (j == n - 1)
{
for (let k = i + 1; k < m; k++)
{
path[idx + k - i] = mat[k][j];
}
for (let l = 0; l < idx + m - i; l++)
{
document.write(path[l] + " ");
}
document.write();
return;
}
// Print all the paths that are possible after moving down
printMatrix(mat, m, n, i + 1, j, path, idx + 1);
// Print all the paths that are possible after moving right
printMatrix(mat, m, n, i, j + 1, path, idx + 1);
}
// Driver code
let m = 2;
let n = 3;
let mat = [[ 1, 2, 3 ],
[ 4, 5, 6 ]];
let maxLengthOfPath = m + n - 1;
printMatrix(mat, m, n, 0, 0, new Array(maxLengthOfPath), 0);
// This code is contributed by ab2127
</script>
Producción
1 4 5 6 1 2 5 6 1 2 3 6
Tenga en cuenta que en el código anterior, la última línea de printAllPathsUtil() está comentada. Si descomentamos esta línea, obtenemos todas las rutas desde la parte superior izquierda hasta la parte inferior derecha de una array nXm si también se permiten los movimientos diagonales. Y también si no se permite moverse a algunas de las celdas, entonces el mismo código se puede mejorar pasando la array de restricción a la función anterior y eso se deja como ejercicio.
Este artículo es una contribución de Hariprasad NG . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
C++
// C++ program to Print all possible paths from
// top left to bottom right of a mXn matrix
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> allPaths;
void findPathsUtil(vector<vector<int>> maze, int m,
int n, int i, int j,
vector<int> path, int index)
{
// If we reach the bottom of maze,
// we can only move right
if (i == m - 1)
{
for(int k = j; k < n; k++)
{
//path.append(maze[i][k])
path[index + k - j] = maze[i][k];
}
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
cout << "[" << path[0] << ", ";
for(int z = 1; z < path.size() - 1; z++)
{
cout << path[z] << ", ";
}
cout << path[path.size() - 1] << "]" << endl;
allPaths.push_back(path);
return;
}
// If we reach to the right most
// corner, we can only move down
if (j == n - 1)
{
for(int k = i; k < m; k++)
{
path[index + k - i] = maze[k][j];
}
//path.append(maze[j][k])
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
cout << "[" << path[0] << ", ";
for(int z = 1; z < path.size() - 1; z++)
{
cout << path[z] << ", ";
}
cout << path[path.size() - 1] << "]" << endl;
allPaths.push_back(path);
return;
}
// Add current element to the path list
//path.append(maze[i][j])
path[index] = maze[i][j];
// Move down in y direction and call
// findPathsUtil recursively
findPathsUtil(maze, m, n, i + 1,
j, path, index + 1);
// Move down in y direction and
// call findPathsUtil recursively
findPathsUtil(maze, m, n, i, j + 1,
path, index + 1);
}
void findPaths(vector<vector<int>> maze,
int m, int n)
{
vector<int> path(m + n - 1, 0);
findPathsUtil(maze, m, n, 0, 0, path, 0);
}
// Driver Code
int main()
{
vector<vector<int>> maze{ { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
findPaths(maze, 3, 3);
//print(allPaths)
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to Print all possible paths from
// top left to bottom right of a mXn matrix
import java.io.*;
import java.util.*;
class GFG
{
static ArrayList<ArrayList<Integer>> allPaths =
new ArrayList<ArrayList<Integer>>();
static void findPathsUtil(ArrayList<ArrayList<Integer>> maze,
int m, int n, int i,int j,
ArrayList<Integer> path,int index)
{
// If we reach the bottom of maze,
// we can only move right
if(i == m - 1)
{
for(int k = j; k < n; k++)
{
// path.append(maze[i][k])
path.set(index + k - j, maze.get(i).get(k));
}
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
System.out.print("[" + path.get(0) + ", ");
for(int z = 1; z < path.size() - 1; z++)
{
System.out.print(path.get(z) + ", ");
}
System.out.println(path.get(path.size() - 1) + "]");
allPaths.add(path);
return;
}
// If we reach to the right most
// corner, we can only move down
if(j == n - 1)
{
for(int k = i; k < m; k++)
{
path.set(index + k - i,maze.get(k).get(j));
}
// path.append(maze[j][k])
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
System.out.print("[" + path.get(0) + ", ");
for(int z = 1; z < path.size() - 1; z++)
{
System.out.print(path.get(z) + ", ");
}
System.out.println(path.get(path.size() - 1) + "]");
allPaths.add(path);
return;
}
// Add current element to the path list
//path.append(maze[i][j])
path.set(index,maze.get(i).get(j));
// Move down in y direction and call
// findPathsUtil recursively
findPathsUtil(maze, m, n, i + 1, j, path, index + 1);
// Move down in y direction and
// call findPathsUtil recursively
findPathsUtil(maze, m, n, i, j + 1, path, index + 1);
}
static void findPaths(ArrayList<ArrayList<Integer>> maze,
int m, int n)
{
ArrayList<Integer> path = new ArrayList<Integer>();
for(int i = 0; i < m + n - 1; i++)
{
path.add(0);
}
findPathsUtil(maze, m, n, 0, 0, path, 0);
}
// Driver code
public static void main (String[] args)
{
ArrayList<ArrayList<Integer>> maze =
new ArrayList<ArrayList<Integer>>();
maze.add(new ArrayList<Integer>
(Arrays.asList(1,2,3)));
maze.add(new ArrayList<Integer>
(Arrays.asList(4,5,6)));
maze.add(new ArrayList<Integer>
(Arrays.asList(7,8,9)));
findPaths(maze, 3, 3);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to Print all possible paths from # top left to bottom right of a mXn matrix allPaths = [] def findPaths(maze,m,n): path = [0 for d in range(m+n-1)] findPathsUtil(maze,m,n,0,0,path,0) def findPathsUtil(maze,m,n,i,j,path,index): global allPaths # if we reach the bottom of maze, we can only move right if i==m-1: for k in range(j,n): #path.append(maze[i][k]) path[index+k-j] = maze[i][k] # if we hit this block, it means one path is completed. # Add it to paths list and print print(path) allPaths.append(path) return # if we reach to the right most corner, we can only move down if j == n-1: for k in range(i,m): path[index+k-i] = maze[k][j] #path.append(maze[j][k]) # if we hit this block, it means one path is completed. # Add it to paths list and print print(path) allPaths.append(path) return # add current element to the path list #path.append(maze[i][j]) path[index] = maze[i][j] # move down in y direction and call findPathsUtil recursively findPathsUtil(maze, m, n, i+1, j, path, index+1) # move down in y direction and call findPathsUtil recursively findPathsUtil(maze, m, n, i, j+1, path, index+1) if __name__ == '__main__': maze = [[1,2,3], [4,5,6], [7,8,9]] findPaths(maze,3,3) #print(allPaths)
C#
// C# program to Print all possible paths from
// top left to bottom right of a mXn matrix
using System;
using System.Collections.Generic;
class GFG
{
static List<List<int>> allPaths = new List<List<int>>();
static void findPathsUtil(List<List<int>> maze,
int m, int n, int i,
int j, List<int> path,
int index)
{
// If we reach the bottom of maze,
// we can only move right
if (i == m - 1)
{
for(int k = j; k < n; k++)
{
// path.append(maze[i][k])
path[index + k - j] = maze[i][k];
}
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
Console.Write( "[" + path[0] + ", ");
for(int z = 1; z < path.Count - 1; z++)
{
Console.Write(path[z] + ", ");
}
Console.WriteLine(path[path.Count - 1] + "]");
allPaths.Add(path);
return;
}
// If we reach to the right most
// corner, we can only move down
if (j == n - 1)
{
for(int k = i; k < m; k++)
{
path[index + k - i] = maze[k][j];
}
// path.append(maze[j][k])
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
Console.Write( "[" + path[0] + ", ");
for(int z = 1; z < path.Count - 1; z++)
{
Console.Write(path[z] + ", ");
}
Console.WriteLine(path[path.Count - 1] + "]");
allPaths.Add(path);
return;
}
// Add current element to the path list
//path.append(maze[i][j])
path[index] = maze[i][j];
// Move down in y direction and call
// findPathsUtil recursively
findPathsUtil(maze, m, n, i + 1,
j, path, index + 1);
// Move down in y direction and
// call findPathsUtil recursively
findPathsUtil(maze, m, n, i, j + 1,
path, index + 1);
}
static void findPaths(List<List<int>> maze, int m, int n)
{
List<int> path = new List<int>();
for(int i = 0; i < m + n - 1; i++)
{
path.Add(0);
}
findPathsUtil(maze, m, n, 0, 0, path, 0);
}
// Driver code
static void Main()
{
List<List<int>> maze = new List<List<int>>();
maze.Add(new List<int> { 1, 2, 3 });
maze.Add(new List<int> { 4, 5, 6 });
maze.Add(new List<int> { 7, 8, 9 });
findPaths(maze, 3, 3);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to Print all possible paths from
// top left to bottom right of a mXn matrix
let allPaths = [];
function findPathsUtil(maze, m, n, i, j, path, index)
{
// If we reach the bottom of maze,
// we can only move right
if (i == m - 1)
{
for(let k = j; k < n; k++)
{
//path.append(maze[i][k])
path[index + k - j] = maze[i][k];
}
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
document.write("[" + path[0] + ", ");
for(let z = 1; z < path.length - 1; z++)
{
document.write(path[z] + ", ");
}
document.write(path[path.length - 1] + "]" + "<br>");
allPaths.push(path);
return;
}
// If we reach to the right most
// corner, we can only move down
if (j == n - 1)
{
for(let k = i; k < m; k++)
{
path[index + k - i] = maze[k][j];
}
// path.append(maze[j][k])
// If we hit this block, it means one
// path is completed. Add it to paths
// list and print
document.write("[" + path[0] + ", ");
for(let z = 1; z < path.length - 1; z++)
{
document.write(path[z] + ", ");
}
document.write(path[path.length - 1] + "]" + "<br>");
allPaths.push(path);
return;
}
// Add current element to the path list
// path.append(maze[i][j])
path[index] = maze[i][j];
// Move down in y direction and call
// findPathsUtil recursively
findPathsUtil(maze, m, n, i + 1,
j, path, index + 1);
// Move down in y direction and
// call findPathsUtil recursively
findPathsUtil(maze, m, n, i, j + 1,
path, index + 1);
}
function findPaths(maze, m, n)
{
let path = new Array(m + n - 1).fill(0);
findPathsUtil(maze, m, n, 0, 0, path, 0);
}
// Driver Code
let maze = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ];
findPaths(maze, 3, 3)
// This code is contributed by Saurabh Jaiswal
</script>
Producción
[1, 4, 7, 8, 9] [1, 4, 5, 8, 9] [1, 4, 5, 6, 9] [1, 2, 5, 8, 9] [1, 2, 5, 6, 9] [1, 2, 3, 6, 9]
Tenga en cuenta que todo el enfoque anterior requiere tiempo y espacio adicionales para resolver el problema, simplemente podemos usar el algoritmo de seguimiento para resolver el problema de manera optimizada
C++
#include<bits/stdc++.h>
using namespace std;
// function to display the path
void display(vector<int> &ans) {
for(auto i :ans ) {
cout<<i <<" ";
}
cout<<endl;
}
// a function which check whether our step is safe or not
bool issafe(int r,int c,vector<vector<int>>& visited,int n,int m) {
return (r < n and c <m and visited[r] !=-1 ); // return true if all values satisfied else false
}
void FindPaths(vector<vector<int>> &grid,int r,int c, int n,int m,vector<int> &ans) {
// when we hit the last cell we reach to destination then directly push the path
if(r == n-1 and c == m-1) {
ans.push_back(grid[r]);
display(ans); // function to display the path stored in ans vector
ans.pop_back(); // pop back because we need to backtrack to explore more path
return ;
}
// we will store the current value in ch and mark the visited place as -1
int ch = grid[r];
ans.push_back(ch); // push the path in ans array
grid[r] = -1; // mark the visited place with -1
// if is it safe to take next downward step then take it
if(issafe(r+1,c,grid,n,m)) {
FindPaths(grid,r+1,c,n,m,ans);
}
// if is it safe to take next rightward step then take it
if(issafe(r,c+1,grid,n,m)) {
FindPaths(grid,r,c+1,n,m,ans);
}
// backtracking step we need to make values original so to we can visit it by some another path
grid[r] = ch;
// remove the current path element we explore
ans.pop_back();
return ;
}
int main() {
int n = 3 ,m =3;
vector<vector<int> >grid{ {1,2,3},{4,5,6},{7,8,9}};
vector<int>ans ; // it will store the path which we have covered
FindPaths(grid,0,0,n,m,ans); // here 0,0 are initial position to start with
return 0;
}
Java
import java.util.*;
class Main {
public static void main(String[] args)
{
int n = 3, m = 3;
int[][] grid
= { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
ArrayList<Integer> ans
= new ArrayList<>(); // it will store the path
// which we have covered
FindPaths(grid, 0, 0, n, m,
ans); // here 0,0 are initial position to
// start with
}
// function to display the path
public static void display(ArrayList<Integer> ans)
{
for (int i : ans) {
System.out.print(i + " ");
}
System.out.println();
}
// a function which check whether our step is safe or
// not
public static boolean
issafe(int r, int c, int[][] visited, int n, int m)
{
return (r < n && c < m && visited[r] != -1);
}
public static void FindPaths(int[][] grid, int r, int c,
int n, int m,
ArrayList<Integer> ans)
{
// when we hit the last cell we reach to destination
// then directly push the path
if (r == n - 1 && c == m - 1) {
ans.add(grid[r]);
display(ans); // function to display the path
// stored in ans vector
ans.remove(
ans.size()
- 1); // remove last element because we need
// to backtrack to explore more path
return;
}
// we will store the current value in ch and mark
// the visited place as -1
int ch = grid[r];
ans.add(ch); // add the path in ans array
grid[r] = -1; // mark the visited place with -1
// if is it safe to take next downward step then
// take it
if (issafe(r + 1, c, grid, n, m)) {
FindPaths(grid, r + 1, c, n, m, ans);
}
// if is it safe to take next rightward step then
// take it
if (issafe(r, c + 1, grid, n, m)) {
FindPaths(grid, r, c + 1, n, m, ans);
}
// backtracking step we need to make values original
// so to we can visit it by some another path
grid[r] = ch;
// remove the current path element we explore
ans.remove(ans.size() - 1);
return;
}
}
// This code is contributed by Tapesh(tapeshdua420)
Python3
# code
class Solution:
def __init__(self):
self.mapping = {}
def printAllPaths(self, M, m, n):
if not self.mapping.get((m,n)):
if m == 1 and n == 1:
return [M[m-1][n-1]]
else:
res = []
if n > 1:
a = self.printAllPaths(M, m, n-1)
for i in a:
if not isinstance(i, list):
i = [i]
res.append(i+[M[m-1][n-1]])
if m > 1:
b = self.printAllPaths(M, m-1, n)
for i in b:
if not isinstance(i, list):
i = [i]
res.append(i+[M[m-1][n-1]])
self.mapping[(m,n)] = res
return self.mapping.get((m,n))
M = [[1, 2, 3], [4, 5, 6], [7,8,9]]
m, n = len(M), len(M[0])
a = Solution()
res = a.printAllPaths(M, m, n)
for i in res:
print(i)
C#
// C# program for above problem
using System;
using System.Collections.Generic;
class Program {
// function to display the path
static void display(List<int> ans)
{
foreach(var i in ans)
{
Console.Write(i + " ");
}
Console.WriteLine();
}
// a function which check whether our step is safe or not
static bool issafe(int r, int c, int[][] visited, int n, int m)
{
return (r < n && c < m && visited[r] != -1); // return true if all values satisfied else false
}
static void FindPaths(int[][] grid, int r, int c, int n, int m, List<int> ans)
{
// when we hit the last cell we reach to destination then directly push the path
if (r == n - 1 && c == m - 1) {
ans.Add(grid[r]);
display(ans); // function to display the path stored in ans vector
ans.RemoveAt(ans.Count - 1); // remove last element because we need to backtrack to explore more path
return;
}
int ch = grid[r]; // we will store the current value in ch and mark the visited place as -1
ans.Add(ch); // add the path in ans array
grid[r] = -1; // mark the visited place with -1
// if is it safe to take next downward step then take it
if (issafe(r + 1, c, grid, n, m)) {
FindPaths(grid, r + 1, c, n, m, ans);
}
// if is it safe to take next rightward step then take it
if (issafe(r, c + 1, grid, n, m)) {
FindPaths(grid, r, c + 1, n, m, ans);
}
// backtracking step we need to make values original so to we can visit it by some another path
grid[r] = ch;
// remove the current path element we explore
ans.RemoveAt(ans.Count - 1);
}
static void Main()
{
int n = 3, m = 3;
int[][] grid = new int[n][];
grid[0] = new[] { 1, 2, 3 };
grid[1] = new[] { 4, 5, 6 };
grid[2] = new[] { 7, 8, 9 };
List<int> ans = new List<int>(); // it will store the path which we have covered
FindPaths(grid, 0, 0, n, m, ans); // here 0,0 are initial position to start with
}
}
// This code is contributed by Tapesh(tapeshdua420)
Producción
1 4 7 8 9 1 4 5 8 9 1 4 5 6 9 1 2 5 8 9 1 2 5 6 9 1 2 3 6 9
Entonces, con este método, puede optimizar su código.
TC- O(2^n*m) , SC – O(n)
Otro enfoque (iterativo):
1. En este enfoque, utilizaremos BFS (búsqueda primero en amplitud) para encontrar todas las rutas posibles.
2. Haremos una cola que contenga la siguiente información:
a) Vector que almacena el camino hasta una determinada celda.
b) coordenadas de la celda.
3. Comenzaremos desde la celda superior izquierda y empujaremos el valor de la celda y las coordenadas en la cola.
4. Seguiremos explorando la celda derecha y abajo (si es posible) hasta que la cola no esté vacía
y colóquelos en la cola actualizando el vector de celda actual.
5. Si llegamos a la última celda, tenemos una respuesta e imprimiremos el vector de respuesta.
C++
// c++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// this structure stores information
// about a particular cell i.e
// path upto that cell and cell's
// coordinates
struct info {
vector<int> path;
int i;
int j;
};
void printAllPaths(vector<vector<int> >& maze)
{
int n = maze.size();
int m = maze[0].size();
queue<info> q;
// pushing top-left cell into the queue
q.push({ { maze[0][0] }, 0, 0 });
while (!q.empty()) {
info p = q.front();
q.pop();
// if we reached the bottom-right cell
// i.e the destination then print the path
if (p.i == n - 1 && p.j == m - 1) {
for (auto x : p.path)
cout << x << " ";
cout << "\n";
}
// if we are in the last row
// then only right movement is possible
else if (p.i == n - 1) {
vector<int> temp = p.path;
// updating the current path
temp.push_back(maze[p.i][p.j + 1]);
q.push({ temp, p.i, p.j + 1 });
}
// if we are in the last column
// then only down movement is possible
else if (p.j == m - 1) {
vector<int> temp = p.path;
// updating the current path
temp.push_back(maze[p.i + 1][p.j]);
q.push({ temp, p.i + 1, p.j });
}
// else both right and down movement
// are possible
else { // right movement
vector<int> temp = p.path;
// updating the current path
temp.push_back(maze[p.i][p.j + 1]);
q.push({ temp, p.i, p.j + 1 });
// down movement
temp.pop_back();
// updating the current path
temp.push_back(maze[p.i + 1][p.j]);
q.push({ temp, p.i + 1, p.j });
}
}
}
// Driver Code
int main()
{
vector<vector<int> > maze{ { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
printAllPaths(maze);
return 0;
}
Python3
# Python implementation for the above approach from collections import deque # this structure stores information # about a particular cell i.e # path upto that cell and cell's # coordinates class info: def __init__(self, path, i, j): self.path = path self.i = i self.j = j def printAllPaths(maze): n = len(maze) m = len(maze[0]) q = deque() # pushing top-left cell into the queue q.append(info([maze[0][0]], 0, 0)) while len(q) > 0: p = q.popleft() # if we reached the bottom-right cell # i.e the destination then print the path if p.i == n - 1 and p.j == m - 1: for x in p.path: print(x, end=" ") print() # if we are in the last row # then only right movement is possible elif p.i == n-1: temp = p.path[:] # updating the current path temp.append(maze[p.i][p.j+1]) q.append(info(temp, p.i, p.j+1)) # if we are in the last column # then only down movement is possible elif p.j == m-1: temp = p.path[:] # updating the current path temp.append(maze[p.i+1][p.j]) q.append(info(temp, p.i+1, p.j)) # else both right and down movement # are possible else: # right movement temp = p.path[:] # updating the current path temp.append(maze[p.i][p.j + 1]) q.append(info(temp, p.i, p.j + 1)) # down movement temp = temp[:-1] # updating the current path temp.append(maze[p.i + 1][p.j]) q.append(info(temp, p.i + 1, p.j)) # Driver Code maze = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] printAllPaths(maze) # This code is contributed by Tapesh(tapeshdua420)
Producción
1 2 3 6 9 1 2 5 6 9 1 2 5 8 9 1 4 5 6 9 1 4 5 8 9 1 4 7 8 9
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