Maze Problem (Using BackTrack)

(You will see error in First Test case ignore that and directly submit the program)

Maze Problem

You are provided a matrix of size N*N with source position at (0,0) and
destination at (N-1,N-1) in a 2D array. Some of the positions in the array are marked as 0 which are blocked cells, rest being marked 1.

A path is a connected sequence of elements from (0,0) to (N-1,N-1) which consists of 1. A sequence of 1s in the 2D array is connected if every 1 in the sequence is adjacent (the above or left neighbour) to the next 1 in the sequence.

For example, in the following matrix,
1 1 0
0 1 1
1 0 1
the 1s marked in blue is a connected path from (0,0) to (2,2)

Note that cells at (0,0) and (N-1,N-1) are always 1. You can either make
movement towards right or down, i.e., from position (x,y), you can go to either the position (x,y+1) or (x+1,y).

Input

First line consists of the size of the input array N (<=50), following that would
be the state of NxN maze which would consist of 0s and 1s.

Output
You have to print "POSSIBLE" if there exists a path between the source and the destination otherwise print "NOT POSSIBLE".

Source Code:

#include<stdio.h>

#define true 1
#define false 0
// Maze size
#define N 52

int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

/* A utility function to print solution matrix 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("\n");
}
}

/* A utility function to check if x,y is valid index for N*N maze */
int isSafe(int maze[N][N], int x, int y)
{
// if (x,y outside maze) return false
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;

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 1s. Please note that
there may be more than one solutions, this function prints one of the feasible
solutions.*/
int 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("NOT POSSIBLE");
return false;
}
printf("POSSIBLE");
// printSolution(sol);
return true;
}

/* A recursive utility function to solve Maze problem */
int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
// if (x,y is goal) return true
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid
if(isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;

/* Move forward in x direction */
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;

/* If moving in x direction doesn't give solution then
Move down in y direction */
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;

/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
sol[x][y] = 0;
return false;
}

return false;
}

// driver program to test above function
int main()
{int n;
scanf("%d",&n);
int maze[52][52] ;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&maze[i][j]);

}
solveMaze(maze);

return 0;
}

Maze Problem C program

Maze Problem (Using BackTrack)

Source Code: