Dada una array mat[][] de dimensión N*M , un entero positivo K y la celda de origen (X, Y) , la tarea es imprimir todas las rutas posibles para salir de la array desde la celda de origen (X, Y ) moviéndose en las cuatro direcciones en cada movimiento en un máximo de K movimientos.
Ejemplos:
Entrada: N = 2, M = 2, X = 1, Y = 1, K = 2
Salida:
(1 1)(1 0)
(1 1)(1 2)(1 3)
(1 1)(1 2 )(0 2)
(1 1)(0 1)
(1 1)(2 1)(2 0)
(1 1)(2 1)(3 1)Entrada: N = 1, M = 1, X = 1, Y = 1, K = 2
Salida:
(1 1)(1 0)
(1 1)(1 2)
(1 1)(0 1)
(1 1 )(2 1)
Enfoque: El problema dado se puede resolver usando Recursion y Backtracking . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array , digamos, arrayOfMoves[] que almacena todos los movimientos que se mueven desde la celda de origen hasta la salida de la array.
- Defina una función recursiva , diga printAllmoves(N, M, move, X, Y, arrayOfMoves) y realice los siguientes pasos:
- Caso base:
- Si el valor de los movimientos no es negativo y la celda actual (X, Y) está fuera de la array, imprima todos los movimientos almacenados en ArrayOfMoves[] .
- Si el valor de los movimientos es menor que 0 , regrese de la función .
- Inserta la celda actual (X, Y) en la array arrayOfMoves[] .
- Llame recursivamente a la función en las cuatro direcciones de la celda actual (X, Y) al disminuir el valor de los movimientos en 1
- Si el tamaño de la array arrayOfMoves[] es mayor que 1, elimine la última celda insertada para los pasos de retroceso.
- Caso base:
- Llame a la función printAllmoves(N, M, move, X, Y, arrayOfMoves) para imprimir todos los movimientos posibles.
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 print all the paths
// that are outside of the matrix
void printAllmoves(
int n, int m, int x, int y,
int moves, vector<pair<int,int>> ArrayOfMoves)
{
// Base Case
if (x <= 0 || y <= 0 || x >= n + 1
|| y >= m + 1 && moves >= 0) {
// Add the last position
ArrayOfMoves.push_back({x, y});
// Traverse the pairs
for (auto ob : ArrayOfMoves) {
// Print all the paths
cout<<"("<<ob.first<<" "<<ob.second<<")";
}
cout<<endl;
// Backtracking Steps
if(ArrayOfMoves.size() > 1)
ArrayOfMoves.pop_back();
return;
}
// If no moves remain
if (moves <= 0) {
return;
}
// Add the current position
// in the list
ArrayOfMoves.push_back({x, y});
// Recursive function Call
// in all the four directions
printAllmoves(n, m, x, y - 1, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x, y + 1, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x - 1, y, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x + 1, y, moves - 1,
ArrayOfMoves);
// Backtracking Steps
if (ArrayOfMoves.size() > 1) {
ArrayOfMoves.pop_back();
}
}
// Driver Code
int main()
{
int N = 2, M = 2;
int X = 1;
int Y = 1;
int K = 2;
vector<pair<int,int>> ArrayOfMoves;
// Function Call
printAllmoves(N, M, X, Y, K,
ArrayOfMoves);
}
// This code is contributed by ipg2016107.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
public class GFG {
// Class for the pairs
static class Pair {
int a;
int b;
Pair(int a, int b)
{
this.a = a;
this.b = b;
}
}
// Function to print all the paths
// that are outside of the matrix
static void printAllmoves(
int n, int m, int x, int y,
int moves, ArrayList<Pair> ArrayOfMoves)
{
// Base Case
if (x <= 0 || y <= 0 || x >= n + 1
|| y >= m + 1 && moves >= 0) {
// Add the last position
ArrayOfMoves.add(new Pair(x, y));
// Traverse the pairs
for (Pair ob : ArrayOfMoves) {
// Print all the paths
System.out.print("(" + ob.a
+ " " + ob.b
+ ")");
}
System.out.println();
// Backtracking Steps
if (ArrayOfMoves.size() > 1)
ArrayOfMoves.remove(
ArrayOfMoves.size() - 1);
return;
}
// If no moves remain
if (moves <= 0) {
return;
}
// Add the current position
// in the list
ArrayOfMoves.add(new Pair(x, y));
// Recursive function Call
// in all the four directions
printAllmoves(n, m, x, y - 1, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x, y + 1, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x - 1, y, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x + 1, y, moves - 1,
ArrayOfMoves);
// Backtracking Steps
if (ArrayOfMoves.size() > 1) {
ArrayOfMoves.remove(
ArrayOfMoves.size() - 1);
}
}
// Driver Code
public static void main(String[] args)
{
int N = 2, M = 2;
int X = 1;
int Y = 1;
int K = 2;
ArrayList<Pair> ArrayOfMoves
= new ArrayList<>();
// Function Call
printAllmoves(N, M, X, Y, K,
ArrayOfMoves);
}
}
Python3
# Python program for the above approach
# Function to print all the paths
# that are outside of the matrix
def printAllmoves(n,m,x,y, moves,ArrayOfMoves):
# Base Case
if (x <= 0 or y <= 0 or x >= n + 1 or y >= m + 1 and moves >= 0):
# Add the last position
ArrayOfMoves.append([x, y])
# Traverse the pairs
for ob in ArrayOfMoves:
# Print all the paths
print("(",ob[0],ob[1],")",end="")
print("\n",end = "")
# Backtracking Steps
if(len(ArrayOfMoves) > 1):
ArrayOfMoves.pop()
return
# If no moves remain
if (moves <= 0):
return
# Add the current position
# in the list
ArrayOfMoves.append([x, y])
# Recursive function Call
# in all the four directions
printAllmoves(n, m, x, y - 1, moves - 1,ArrayOfMoves)
printAllmoves(n, m, x, y + 1, moves - 1,ArrayOfMoves)
printAllmoves(n, m, x - 1, y, moves - 1,ArrayOfMoves)
printAllmoves(n, m, x + 1, y, moves - 1,ArrayOfMoves)
# Backtracking Steps
if (len(ArrayOfMoves) > 1):
ArrayOfMoves.pop()
# Driver Code
if __name__ == '__main__':
N = 2
M = 2
X = 1
Y = 1
K = 2
ArrayOfMoves = []
# Function Call
printAllmoves(N, M, X, Y, K,ArrayOfMoves)
# This code is contributed by SURENDRA_GANGWAR.
C#
using System;
using System.Collections;
public class GFG {
class Pair {
public int a;
public int b;
public Pair(int a, int b)
{
this.a = a;
this.b = b;
}
}
// Function to print all the paths
// that are outside of the matrix
static void printAllmoves(int n, int m, int x, int y,
int moves,
ArrayList ArrayOfMoves)
{
// Base Case
if (x <= 0 || y <= 0 || x >= n + 1
|| y >= m + 1 && moves >= 0) {
// Add the last position
ArrayOfMoves.Add(new Pair(x, y));
// Traverse the pairs
foreach (Pair ob in ArrayOfMoves) {
// Print all the paths
Console.Write("(" + ob.a + " " + ob.b
+ ")");
}
Console.WriteLine();
// Backtracking Steps
if (ArrayOfMoves.Count > 1)
ArrayOfMoves.Remove(ArrayOfMoves.Count
- 1);
return;
}
// If no moves remain
if (moves <= 0) {
return;
}
// Add the current position
// in the list
ArrayOfMoves.Add(new Pair(x, y));
// Recursive function Call
// in all the four directions
printAllmoves(n, m, x, y - 1, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x, y + 1, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x - 1, y, moves - 1,
ArrayOfMoves);
printAllmoves(n, m, x + 1, y, moves - 1,
ArrayOfMoves);
// Backtracking Steps
if (ArrayOfMoves.Count > 1) {
ArrayOfMoves.Remove(ArrayOfMoves.Count - 1);
}
}
static public void Main()
{
int N = 2, M = 2;
int X = 1;
int Y = 1;
int K = 2;
ArrayList ArrayOfMoves = new ArrayList();
// Function Call
printAllmoves(N, M, X, Y, K, ArrayOfMoves);
}
}
// This code is contributed by maddler.
Javascript
<script>
// Javascript program for the above approach
// Class for the pairs
class Pair {
constructor(a , b) {
this.a = a;
this.b = b;
}
}
function ob(item)
{
// Print all the paths
document.write("(" + item.a + " " + item.b + ")");
}
// Function to print all the paths
// that are outside of the matrix
function printAllmoves(n , m , x , y , moves, ArrayOfMoves)
{
// Base Case
if (x <= 0 || y <= 0 || x >= n + 1 || y >= m + 1 && moves >= 0) {
// Add the last position
ArrayOfMoves.push(new Pair(x, y));
// Traverse the pairs
ArrayOfMoves.forEach (ob);
document.write("<br/>");
// Backtracking Steps
if (ArrayOfMoves.length > 1)
ArrayOfMoves.pop(ArrayOfMoves.length - 1);
return;
}
// If no moves remain
if (moves <= 0) {
return;
}
// Add the current position
// in the list
ArrayOfMoves.push(new Pair(x, y));
// Recursive function Call
// in all the four directions
printAllmoves(n, m, x, y - 1, moves - 1, ArrayOfMoves);
printAllmoves(n, m, x, y + 1, moves - 1, ArrayOfMoves);
printAllmoves(n, m, x - 1, y, moves - 1, ArrayOfMoves);
printAllmoves(n, m, x + 1, y, moves - 1, ArrayOfMoves);
// Backtracking Steps
if (ArrayOfMoves.length > 1) {
ArrayOfMoves.pop(ArrayOfMoves.length - 1);
}
}
// Driver Code
var N = 2, M = 2;
var X = 1;
var Y = 1;
var K = 2;
var ArrayOfMoves =new Array();
// Function Call
printAllmoves(N, M, X, Y, K, ArrayOfMoves);
// This code is contributed by gauravrajput1
</script>
Producción:
(1 1)(1 0) (1 1)(1 2)(1 3) (1 1)(1 2)(0 2) (1 1)(0 1) (1 1)(2 1)(2 0) (1 1)(2 1)(3 1)
Complejidad de Tiempo: O(4 N )
Espacio Auxiliar: O(4 N )
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA