// MAZE PROGRAM - ASSIGNMENT 1
// PROGRAMMER : G.PAVAN KUMAR


#include<iostream.h>
#include<fstream.h>

class stack
{ 
     	struct data  //declared stack using struct inorder to make code effective
	{   int x;
          int y;  //x,y gives row-column details
      }q[100];
 	int top;

  public:
 
	stack()  // declaration of constructor for initialization
   	{
      	top=0;
      }
	
      void push(int a, int b)
      {  
	   if(top > 100)      // condition for stack limit
     	   cout<<"stackfull";
     	   else
	   { q[top].x=a;
	     q[top].y=b;
	     top++;
         }	
     }
 
   void pop()
 
   { if(top >0)
 
     { 
	   top--;
	   
     }
  
    else //verifying for empty stack poping
   
	    cout<<"empty stack";
 
   }

    
  
   void display(int m,int n,int **p)//displays path
 
   {  
	   int a,b;
	   
	   fstream outf;
	   fstream out1f;
	   outf.open("text9.txt",ios::app);//storing output
	   out1f.open("stack1",ios::app);//stack output
           out1f<<"stack content"<<endl<<endl;
	   for(int i=0;i<top;i++)
           
	   {
		   a=q[i].x;
	           b=q[i].y;
                   out1f<<a<<b<<endl;
		   p[a][b]=9;
           
	   }
	   out1f<<endl<<endl;
	   out1f.close();
    
       
	   for(int i=0;i<m;i++)
        
		   for(int j=0;j<n;j++)
        
		   {       if(j%n==0)
		
			   { cout<<endl;
			     outf<<endl;
		           }	     
	      	           
			   if(p[i][j]==9|| (i==1&& j==1))
		
			   { cout<<'*';		
		             outf<<'*';
			   }  
			   else
		
			   { if((i!=0)&&(j!=0)&&(i!=m-1)&&(j!=n-1))
		              cout<<'@';
			      outf<<'@';
		           }	      
                           	
		   }     cout<<endl<<endl<<endl;
                         outf<<endl<<endl<<endl;	   
 }   //end of function display


};//end of class stacK


class maze

{    
	int **p;//dynamically accepting size of matrix
     
	int m,n,s,t;
     
	stack l;// declaration of an object for stack

public:
   
	maze(int a,int b )
   
	{ 
		    
		m=a+2;
     
		n=b+2;//incrementing m,n inorder to construct a boundary of 1's
     
		p=new int*[m];//dynamic initialization
    
	       	for(int i=0;i<m;i++)
     
			p[i]=new int[n];
                        s=1;
		        t=1;	

	}	
     

	   void accept(int a)
   
	   {
	  
          
		   if((s>0)&&(s<m-1)&&(t>0)&&(t<n-1))
	     
		   { 
			   p[s][t]=a;
	      
			   t=t+1;
	      
           
		   }	       
	    
         		    
	    
		   if(t==n-1)
	  
		   { s=s+1;
             
			   t=1;
           
		   }
             	    
	  	       
		
     
		   for(int i=0;i<m;i++)
     
		   {
	     
			   p[i][0]=1;
      
	     
			   p[i][n-1]=1;
     
     
		   }      
     		   
     
		   for(int j=0;j<n;j++)
     
		   { 
	   
			   p[0][j]=1;
       
	     
			   p[m-1][j]=1;
     
     
		   }       
	   }
    	
 
	void travel(int i, int j);

};
void maze :: travel(int i, int j)
{  
	if(!((i==m-2)&&(j==n-2)))//condition for solution
 {// This program relies on recursion.Here we are looking downward then right
  // then upward and at last left
	 // we are changing values of matrix by 2 and 3
	 // 3 - to indicate already entered path
	 // 2 - to prohibit from going inorder to eliminate infinite loop	 
   if(p[i+1][j]==0)
  
   {
	   l.push(i+1,j);
    
	   p[i][j]=3;//changing the value inorder to safe guard from infinet                      //loops
    
	   travel(i+1,j);//recursion call
    
   }
   else
   { 
	   if(p[i][j+1]==0)
     
	   { l.push(i,j+1);
       
		   p[i][j]=3;
   
	       	   travel(i,j+1);
      
     
	   }
    
	   else
    
	   { if(p[i-1][j]==0)
      
		   {l.push(i-1,j);
       
			   p[i][j]=3;
       
			   travel(i-1,j);
       
      
		   }
     
		   else
    
		   {  if(p[i][j-1]==0)
        
			   { l.push(i,j-1);
          
				   p[i][j]=3;
          
				   travel(i,j-1);
	  
       
			   }

		    	   else
        
			   { if(p[i+1][j]==3)
          
				   { p[i][j]=2;
          
					   l.pop();
           
					   travel(i+1,j);
          
	
				   }
         
				   else
          {  
		  if(p[i][j+1]==3)
             
		  { 
			  p[i][j]=2;
               
			  l.pop();
             
			  travel(i,j+1);
             
		  }
           
		  else
            
		  {
              
			  if(p[i-1][j]==3)
              
			  {
				  p[i][j]=2;
                
				  l.pop();
                
				  travel(i-1,j);
	      
			  }
             
			  else
             
			  { 
				  if(p[i][j-1]==3)
               
				  { 
					  p[i][j]=2;
                 
					  l.pop();
                 
					  travel(i,j-1);
               
				  }
              
				  else
              
				  {       cout<<endl<<"path not found"<<endl;
					  l.display(m,n,p);
					  
				    
			          }	    
            
			  }
      
		  }
	  
	  }
    
			   
			   }
	}	  
	  	  
        
    
	   }
  
   }
 }
   
 
	else
 
	{ 
	        cout<<endl<<"solution"<<endl;
 
	      	l.display(m,n,p);//displays solution
 
	}

}
   
   
   void main()
	
   {       int m,n,l;
	   ifstream inf("text.txt");
           while(inf.eof()==0)
          {		   
	   inf>>m;
	   inf>>n;  
	   if(m>20 || n>20)//condition for exceeding limit
           cout<<"MAZE SIZE EXCEEDS LIMIT"<<endl;		   
           maze eg(m,n);
           for(int i=0;i<m;i++)
           for(int j=0;j<n;j++)
           {inf>>l;
            eg.accept(l);
	    
           }	    
	    eg.travel(1,1);
	  }
	 if(inf.eof()!=0)
	  cout<<"end of file";      	 
  
   }//end of main