Given a matrix mat[][] of dimension N*M, a positive integer K and the source cell (X, Y), the task is to print all possible paths to move out of the matrix from the source cell (X, Y) by moving in all four directions in each move in at most K moves.
Examples:
Input: N = 2, M = 2, X = 1, Y = 1, K = 2
Output:
(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)Input: N = 1, M = 1, X = 1, Y = 1, K = 2
Output:
(1 1)(1 0)
(1 1)(1 2)
(1 1)(0 1)
(1 1)(2 1)
Approach: The given problem can be solved by using Recursion and Backtracking. Follow the steps below to solve the given problem:
- Initialize an array, say, arrayOfMoves[] that stores all the moves moving from the source cell to the out of the matrix.
- Define a recursive function, say printAllmoves(N, M, moves, X, Y, arrayOfMoves), and perform the following steps:
- Base Case:
- If the value of the moves is non-negative and the current cell (X, Y) is out of the matrix, then print all the moves stored in the ArrayOfMoves[].
- If the value of moves is less than 0 then return from the function.
- Insert the current cell (X, Y) in the array arrayOfMoves[].
- Recursively call the function in all the four directions of the current cell (X, Y) by decrementing the value of moves by 1
- If the size of the array arrayOfMoves[] is greater than 1, then remove the last cell inserted for the Backtracking steps.
- Base Case:
- Call the function printAllmoves(N, M, moves, X, Y, arrayOfMoves) to print all possible moves.
Below is the implementation of the above approach:
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 matrixvoid 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 Codeint 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 approachimport 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 matrixdef 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 Codeif __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> |
Output:
(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)
Time Complexity: O(4N)
Auxiliary Space: O(4N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
