Print path from given Source to Destination in 2 | C ++ program for printing a path from given source to destination ; Function to print the path ; Base condition ; Pop stores elements ; Recursive call for printing stack In reverse order ; Function to store the path into The stack , if path exist ; Base condition ; Push current elements ; Condition to check whether reach to the Destination or not ; Increment ' x ' ordinate of source by ( 2 * x + y ) Keeping ' y ' constant ; Increment ' y ' ordinate of source by ( 2 * y + x ) Keeping ' x ' constant ; Pop current elements form stack ; If no path exists ; Utility function to check whether path exist or not ; To store x co - ordinate ; To store y co - ordinate ; Function to find the path ; Print - 1 , if path doesn 't exist ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printExistPath ( stack < int > sx , stack < int > sy , int last ) { if ( sx . empty ( ) || sy . empty ( ) ) { return ; } int x = sx . top ( ) ; int y = sy . top ( ) ; sx . pop ( ) ; sy . pop ( ) ; printExistPath ( sx , sy , last ) ; if ( sx . size ( ) == last - 1 ) { cout << " ( " << x << " , ▁ " << y << " ) " ; } else { cout << " ( " << x << " , ▁ " << y << " ) ▁ - > ▁ " ; } } bool storePath ( int srcX , int srcY , int destX , int destY , stack < int > & sx , stack < int > & sy ) { if ( srcX > destX srcY > destY ) { return false ; } sx . push ( srcX ) ; sy . push ( srcY ) ; if ( srcX == destX && srcY == destY ) { printExistPath ( sx , sy , sx . size ( ) ) ; return true ; } if ( storePath ( ( 2 * srcX ) + srcY , srcY , destX , destY , sx , sy ) ) { return true ; } if ( storePath ( srcX , ( 2 * srcY ) + srcX , destX , destY , sx , sy ) ) { return true ; } sx . pop ( ) ; sy . pop ( ) ; return false ; } bool isPathExist ( int srcX , int srcY , int destX , int destY ) { stack < int > sx ; stack < int > sy ; return storePath ( srcX , srcY , destX , destY , sx , sy ) ; } void printPath ( int srcX , int srcY , int destX , int destY ) { if ( ! isPathExist ( srcX , srcY , destX , destY ) ) { cout << " - 1" ; } } int main ( ) { int srcX = 5 , srcY = 8 ; int destX = 83 , destY = 21 ; printPath ( srcX , srcY , destX , destY ) ; }