Dada una array 2-D mat[][] , un origen ‘ s ‘ y un destino ‘ d ‘, imprima todas las rutas únicas desde ‘ s ‘ a ‘ d ‘ dados. Desde cada celda, puede moverse solo hacia la derecha o hacia abajo.
Ejemplos:
Entrada: mat[][] = {{1, 2, 3}, {4, 5, 6}}, s[] = {0, 0}, d[]={1, 2}
Salida:
1 4 5 6
1 2 5 6
1 2 3 6Entrada : mat[][] = {{1, 2}, {3, 4}}, s[] = {0, 1}, d[] = {1, 1}
Salida: 2 4
Enfoque: use la recursión para moverse primero a la derecha y luego hacia abajo desde cada celda en la ruta de la array mat[][] , comenzando desde la fuente, y almacene cada valor en un vector. Si se alcanza el destino, imprima el vector como una de las rutas posibles. Siga los pasos a continuación para resolver el problema:
- Si la celda actual está fuera del límite, entonces regrese.
- Inserte el valor de la celda actual en la ruta del vector [].
- Si la celda actual es el destino, imprima la ruta actual.
- Llame a la misma función para los valores {i+1, j} y {i, j+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;
vector<vector<int> > mat;
vector<int> s;
vector<int> d;
int m = 2, n = 3;
// Function to print all the paths
void printVector(vector<int> path)
{
int cnt = path.size();
for (int i = 0; i < cnt; i += 2)
cout << mat[path[i]][path[i + 1]]
<< " ";
cout << endl;
}
// Function to find all the paths recursively
void countPaths(int i, int j, vector<int> path)
{
// Base Case
if (i > d[0] || j > d[1])
return;
path.push_back(i);
path.push_back(j);
// Destination is reached
if (i == d[0] && j == d[1]) {
printVector(path);
return;
}
// Calling the function
countPaths(i, j + 1, path);
countPaths(i + 1, j, path);
}
// DriverCode
int main()
{
mat = { { 1, 2, 3 },
{ 4, 5, 6 } };
s = { 0, 0 };
d = { 1, 2 };
vector<int> path;
countPaths(s[0], s[1], path);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static Vector<Integer> s = new Vector<>();
static Vector<Integer> d = new Vector<>();
static int m = 2, n = 3;
// Function to print all the paths
static void printVector(Vector<Integer> path, int[][] mat)
{
int cnt = path.size();
for (int i = 0; i < cnt; i += 2)
System.out.print(mat[path.get(i)][path.get(i + 1)]+ " ");
System.out.println();
}
// Function to find all the paths recursively
static void countPaths(int i, int j, Vector<Integer> path, int[][]mat)
{
// Base Case
if (i > d.get(0) || j > d.get(1))
return;
path.add(i);
path.add(j);
// Destination is reached
if (i == d.get(0) && j == d.get(1)) {
printVector(path,mat);
path.remove(path.size()-1);
path.remove(path.size()-1);
return;
}
// Calling the function
countPaths(i, j + 1, path,mat);
countPaths(i + 1, j, path,mat);
path.remove(path.size()-1);
path.remove(path.size()-1);
}
// DriverCode
public static void main(String[] args) {
int[][] mat = {{ 1, 2, 3 },
{ 4, 5, 6 } };
s.add(0);
s.add(0);
d.add(1);
d.add(2);
Vector<Integer> path = new Vector<>();
countPaths(s.get(0), s.get(1), path, mat);
}
}
// This code is contributed by Rajput-Ji.
Python3
# Python code for the above approach
mat = None
s = None
d = None
m = 2
n = 3
# Function to print all the paths
def printVector(path):
cnt = len(path)
for i in range(0, cnt, 2):
print(mat[path[i]][path[i + 1]], end=" ")
print("")
# Function to find all the paths recursively
def countPaths(i, j, path):
# Base Case
if (i > d[0] or j > d[1]):
return
path.append(i)
path.append(j)
# Destination is reached
if (i == d[0] and j == d[1]):
printVector(path)
path.pop()
path.pop()
return
# Calling the function
countPaths(i, j + 1, path)
countPaths(i + 1, j, path)
path.pop()
path.pop()
# DriverCode
mat = [[1, 2, 3],
[4, 5, 6]]
s = [0, 0]
d = [1, 2]
path = []
countPaths(s[0], s[1], path)
# This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
static List<int> s = new List<int>();
static List<int> d = new List<int>();
static int m = 2, n = 3;
// Function to print all the paths
static void printList(List<int> path, int[,] mat)
{
int cnt = path.Count;
for (int i = 0; i < cnt; i += 2)
Console.Write(mat[path[i],path[i + 1]] + " ");
Console.WriteLine();
}
// Function to find all the paths recursively
static void countPaths(int i, int j,
List<int> path, int[,] mat)
{
// Base Case
if (i > d[0] || j > d[1])
return;
path.Add(i);
path.Add(j);
// Destination is reached
if (i == d[0] && j == d[1]) {
printList(path, mat);
path.RemoveAt(path.Count - 1);
path.RemoveAt(path.Count - 1);
return;
}
// Calling the function
countPaths(i, j + 1, path, mat);
countPaths(i + 1, j, path, mat);
path.RemoveAt(path.Count - 1);
path.RemoveAt(path.Count - 1);
}
// DriverCode
public static void Main(String[] args)
{
int[,] mat = { { 1, 2, 3 }, { 4, 5, 6 } };
s.Add(0);
s.Add(0);
d.Add(1);
d.Add(2);
List<int> path = new List<int>();
countPaths(s[0], s[1], path, mat);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
let mat;
let s;
let d;
let m = 2, n = 3;
// Function to print all the paths
function printVector(path) {
let cnt = path.length;
for (let i = 0; i < cnt; i += 2)
document.write(mat[path[i]][path[i + 1]] + " ")
document.write("<br>")
}
// Function to find all the paths recursively
function countPaths(i, j, path)
{
// Base Case
if (i > d[0] || j > d[1])
return;
path.push(i);
path.push(j);
// Destination is reached
if (i == d[0] && j == d[1]) {
printVector(path);
path.pop();
path.pop();
return;
}
// Calling the function
countPaths(i, j + 1, path);
countPaths(i + 1, j, path);
path.pop();
path.pop();
}
// DriverCode
mat = [[1, 2, 3],
[4, 5, 6]];
s = [0, 0];
d = [1, 2];
let path = [];
countPaths(s[0], s[1], path);
// This code is contributed by Potta Lokesh
</script>
Producción:
1 2 3 6 1 2 5 6 1 4 5 6
Complejidad de Tiempo: O(2 n+m )
Espacio Auxiliar: O(1)