Rat in a Maze with multiple steps or jump allowed | C / C ++ program to solve Rat in a Maze problem using backtracking ; Maze size ; A utility function to print solution matrix sol [ N ] [ N ] ; A utility function to check if x , y is valid index for N * N maze ; if ( x , y outside maze ) return false ; This function solves the Maze problem using Backtracking . It mainly uses solveMazeUtil ( ) to solve the problem . It returns false if no path is possible , otherwise return true and prints the path in the form of 1 s . Please note that there may be more than one solutions , this function prints one of the feasible solutions . ; A recursive utility function to solve Maze problem ; if ( x , y is goal ) return true ; Check if maze [ x ] [ y ] is valid ; mark x , y as part of solution path ; Move forward in x direction ; Move forward in x direction ; If moving in x direction doesn 't give  solution then Move down in y direction  ; If none of the above movements work then BACKTRACK : unmark x , y as part of solution path ; driver program to test above function
#include <stdio.h> NEW_LINE #define N  4 NEW_LINE bool solveMazeUtil ( int maze [ N ] [ N ] , int x , int y , int sol [ N ] [ N ] ) ; void printSolution ( int sol [ N ] [ N ] ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) printf ( " ▁ % d ▁ " , sol [ i ] [ j ] ) ; printf ( " STRNEWLINE " ) ; } } bool isSafe ( int maze [ N ] [ N ] , int x , int y ) { if ( x >= 0 && x < N && y >= 0 && y < N && maze [ x ] [ y ] != 0 ) return true ; return false ; } bool solveMaze ( int maze [ N ] [ N ] ) { int sol [ N ] [ N ] = { { 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 } } ; if ( solveMazeUtil ( maze , 0 , 0 , sol ) == false ) { printf ( " Solution ▁ doesn ' t ▁ exist " ) ; return false ; } printSolution ( sol ) ; return true ; } bool solveMazeUtil ( int maze [ N ] [ N ] , int x , int y , int sol [ N ] [ N ] ) { if ( x == N - 1 && y == N - 1 ) { sol [ x ] [ y ] = 1 ; return true ; } if ( isSafe ( maze , x , y ) == true ) { sol [ x ] [ y ] = 1 ; for ( int i = 1 ; i <= maze [ x ] [ y ] && i < N ; i ++ ) { if ( solveMazeUtil ( maze , x + i , y , sol ) == true ) return true ; if ( solveMazeUtil ( maze , x , y + i , sol ) == true ) return true ; } sol [ x ] [ y ] = 0 ; return false ; } return false ; } int main ( ) { int maze [ N ] [ N ] = { { 2 , 1 , 0 , 0 } , { 3 , 0 , 0 , 1 } , { 0 , 1 , 0 , 1 } , { 0 , 0 , 0 , 1 } } ; solveMaze ( maze ) ; return 0 ; }