#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

void find_path_in_maze(int,int,char,int);

char *maze;

int row,col,*trow,*tcol;

void main(void)

 {

 int obst,i,x,y;

 char ans;

 do{

 clrscr();

 printf("\nEnter the maximum row value : ");

 scanf("%d",&row);

 printf("\nEnter the maximum column value : ");

 scanf("%d",&col);

 maze=(char*)calloc(row*col,sizeof(char));

 trow=(int*)malloc(row*col*sizeof(int));

 tcol=(int*)malloc(row*col*sizeof(int));

 printf("\nEnter number of obstructions present :");

 scanf("%d",&obst);

 printf("\n\n");

 for(i=0;i<obst;i++)

  {

  printf("\n\tEnter %d obstruction row position : ",i+1);

  scanf("%d",&x);

  printf("\n\tEnter %d obstruction column position : ",i+1);

  scanf("%d",&y);

  *(maze + x*col + y)='b';

  }

 printf("\n\nDisplaying MAZE Plan :\n\n\t\t");

 for(x=0;x<row;x++)

  {

  for(y=0;y<col;y++)

   if(*(maze + x*col + y)=='b')

    printf(" %c  ",219);

   else

    printf(" %c  ",254);

  printf("\n\n\t\t");

  }

 printf("\n\t\tIs it OK (y/n)?");

 ans=getche();

 }while(ans=='n' || ans=='N');

 find_path_in_maze(0,0,NULL,0);

 }



int flag;

void find_path_in_maze(int r,int c,char pos,int count)

 {

 /*if(count<15)

 printf("%d) %d,%d,%c\n",count,r,c,pos);

 else exit(-9);*/

 if(r<0 || r>=row || c<0 || c>=col)   //Boundary conditions

  return;

 if(r==0 && c==0 && pos!=NULL)    //Loop Check

  return;

 if(r==(row-1) && c==(col-1) && *(maze + r*col + c)!='b')   //Path found

  {

  printf("\n\n\n\t\tPath Found...\n\n");

  for(int i=0;i<count;i++)

   printf("(%d, %d)---",trow[i],tcol[i]);

  printf("(%d, %d)\n",row-1,col-1);

  /*for(int x=0;x<row;x++)

   {

   printf("\n\n\t\t");

   for(int y=0;y<col;y++)

    {

    flag=0;

    if(*(maze + x*col + y)=='b')

     {

     printf(" %c  ",219);

     flag=1;

     }

    else

     {

     for(i=0;i<count;i++)

      if(x==trow[i] && y==tcol[i])

       {

       printf(" *  ");

       flag=1;

       }

     }

    if(!flag)

     if(x!=(row-1) || y!=(col-1))

      printf(" %c  ",254);

    }

  }

  printf(" *  ");*/

  getch();

  exit(0);

  }

 if(*(maze + r*col + c)!='b' && pos!='l')   //Ist priority RIGHT

  {

  trow[count]=r;

  tcol[count]=c;

  find_path_in_maze(r,c+1,'r',count+1);

  }

 if(*(maze + r*col + c)!='b' && pos!='u')  //IInd priority DOWN

  {

  trow[count]=r;

  tcol[count]=c;

  find_path_in_maze(r+1,c,'d',count+1);

  }

 if(*(maze + r*col + c)!='b' && pos!='r')  //IIIrd priority LEFT

  {

  trow[count]=r;

  tcol[count]=c;

  find_path_in_maze(r,c-1,'l',count+1);

  }

 if(*(maze + r*col + c)!='b' && pos!='d')  //IVth priority UP

  {

  trow[count]=r;

  tcol[count]=c;

  find_path_in_maze(r-1,c,'u',count+1);

  }

 if(r==0 && c==0)    //No path found

  {

  printf("\n\n\t\tNo path exists from (0,0) to (%d,%d)",row-1,col-1);

  getch();

  exit(-1);

  }

 }