write a program for finding the path in maze from, begin to end

write a program for finding the path in maze from, begin to end

ABOUT FIGURE:Deep blue indicates wall and deep green denotes free path.

In above figure , upper matrix is input
In below matrix is output (path in form of 1)

CONDITION: movement takeplace ony in positive x direction 
                 and in negative y direction

APPROCH :

 a)in a maze 1 denote movement space and 0 denote wall

  b)use recursion to find the way by reducing number of box

  c)use a new_array which initialisation by 0,and after getting path 
       become 1 on that place.

  D) use BACKTRACKING ,if_rat will not get path then it take back the path
     this_ is known as backtracking.

backtracking

(algorithmic technique)

Definition: Find a solution by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points and alternate choices using recursion.

      /* Programming in C++ */
  
#include<iostream>
using  namespace std ;

const int N=5;

bool ispath( int arr[][N], int x,int y,int n)
{  if (x<n && y< n && arr[x][y]==1)
     {
         return true;
        
     }
return false;
   
}
 
bool pathofmaze(int arr[N][N],int x,int y,int n ,int solarr[][N])             
{
     if( y==(n)&& x==(n-1) )  //base condition       
          {
             solarr[x][y]==1;   
              return true; 
          }
           
      if ( ispath(arr,x,y,n) )
       { 
       
       solarr[x][y]=1;
         if(pathofmaze(arr,x,y+1,n,solarr))
           {
              return true; 
           }     
         if(pathofmaze(arr,x+1,y,n,solarr) )
           {
              return true;
           }
      
          solarr[x][y]=0;// backtracking
       
          return false;
        }
      return false;
   }
   
   
   int main()
{     
       int n=5,i,j;
      
     int arr[N][N] ={{1,0,1,0,1},{1,1,1,1,0},{0,1,0,1,0},{1,0,0,1,1},{1,0,1,0,1}};

     int solarr[N][N]={0};
   
      for(i=0;i<n;i++)

         { for(j=0;j<n;j++)
            {
              cout<<arr[i][j]<<" ";
            }
           cout<<endl;
        }
        cout<<endl;
         
           
           
           
        if(pathofmaze(arr,0,0,5,solarr))     
       {   
           for(i=0;i<n;i++)
           {
               for(j=0;j<n;j++)
                 {
                     cout<<solarr[i][j]<<" ";
                  }
            cout<<endl;
            }
          
       }
           
           
    return 0;
}

Click on the below link and run this program.

https://onlinegdb.com/Sy7iNynHd