Rat_in_a_Maze

//Author : Asim K Prasad
//Program to solve Rat-In-A-Maze problem and then print a valid path too
//The program tracks for a path from top-left corner to the bottom-right corner ONLY
//So the (0,0) && (n-1,m-1) cells should be 1 for a valid path to exist

#include<stdio.h>

#define wl(n) while(n--)
#define fl(i,a,b) for(i=a; i<b; i++)
#define rev(i,a,b) for(i=a; i>=b; i--)
#define scan(n) scanf("%d", &n)
#define scans(s) scanf("%s", s)
#define scanc(c) scanf("%c", &c)
#define scanp(f) scanf("%f", &f)
#define print(n) printf("%d\n", n)
#define prints(s) printf("%s\n", s)
#define printc(c) printf("%c\n", c)
#define printp(f) printf("%f\n", f)
#define nline printf("\n")
#define mclr(strn) strn.clear()
#define ignr cin.ignore()
#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define true 1
#define false 0
#define PB push_back
#define SZ size

int n, m;
int sx, sy;
int tx, ty;

void ans(int ans_mat[100][100])
{
    int i, j;
    fl(i,0,n)
    {
        fl(j,0,m)
             printf(" %d ", ans_mat[i][j]);
        nline;
    }
}

int isOk(int maze[100][100], int x, int y)
{
    if(x>=0 && x<n && y>=0 && y<m && maze[x][y]==1)
        return true;
    return false;
}
int Magic(int maze[100][100], int x, int y, int ans_mat[100][100])
{
     if(x==n-1 && y==m-1)
     {
         ans_mat[x][y] = 1;
        printf("The solution path : ");
        nline;
        ans(ans_mat);
         return 1;
     }

     if(isOk(maze, x, y)==1)
     {
         ans_mat[x][y] = 1;
         //Checking the adjacent blocks for a valid path and then
         //recursively checking adjacent
         //blocks for their valid paths
         if(isOk(maze,x+1,y+1) && ans_mat[x+1][y+1]==0 && Magic(maze,x+1,y+1,ans_mat)==1 )
                return 1;
         if(isOk(maze,x+1,y) && ans_mat[x+1][y]==0 && Magic(maze,x+1,y,ans_mat)==1)
                return 1;
         if(isOk(maze,x,y+1) && ans_mat[x][y+1]==0 && Magic(maze,x,y+1,ans_mat)==1)
                return 1;
         if(isOk(maze,x-1,y) && ans_mat[x-1][y]==0 && Magic(maze,x-1,y,ans_mat)==1  )
                return 1;
         if(isOk(maze,x-1,y+1) && ans_mat[x-1][y+1]==0 && Magic(maze,x-1,y+1,ans_mat)==1 )
                return 1;
         if(isOk(maze,x+1,y-1) && ans_mat[x+1][y-1]==0 && Magic(maze,x+1,y-1,ans_mat)==1)
                 return 1;
         if(isOk(maze,x,y-1) && ans_mat[x][y-1]==0 && Magic(maze,x,y-1,ans_mat)==1)
                return 1;
         if(isOk(maze,x-1,y-1) && ans_mat[x-1][y-1]==0 && Magic(maze,x-1,y-1,ans_mat)==1)
                 return 1;
         ans_mat[x][y] = 0;  //Setting the block to 0 if there is no
                                //valid path through it
         return 0;
     }
     return 0;
}

int arr[1000006];
int reveal(int maze[100][100])
{
     int ans_mat[100][100];
     int i, j;
     int k=0;
     if(Magic(maze,0,0,ans_mat)==false)
     {
           printf("Blocked :( ");   //Blocked condition
           nline;
           return false;
     }
     //printf("valid");
     nline;
     return true;
}

int maze[100][100];

int main()
{
    printf("Enter the number of rows and columns : ");
        scan(n); scan(m);
        int i ,j;
        printf("Enter the matrix ('0' for blocked path, '1' for allowed path) : \n");
        fl(i,0,n)
            fl(j,0,m)
                scan(maze[i][j]);
        reveal(maze);
        return 0;
}