Code:
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
// Maze size
#define N 9
bool 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])
{
int i,j;
for (i = 0; i < N; i++)
{
for (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 */
bool isSafe(int maze[N][N], int x, int y, int gone[N][N])
{
// if (x,y outside maze) return false
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1 && gone[x][y]==0)
return true;
return false;
}
/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
// if (x,y is goal) return true
static int gone[N][N];
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, gone) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;
gone[x][y]=1;
if (solveMazeUtil(maze, x+1, y+1, sol) == true)
return true;
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;
if (solveMazeUtil(maze, x-1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x+1, y-1, sol) == true)
return true;
if (solveMazeUtil(maze, x-1, y+1, sol) == true)
return true;
if (solveMazeUtil(maze, x-1, y-1, sol) == true)
return true;
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 maze[N][N] = {
{1, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 1, 0},
{0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 1, 0, 0, 1, 0, 0, 0, 1},
{1, 0, 0, 1, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 1, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1, 0, 1},
{0, 1, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 1, 0, 0, 1}
};
solveMaze(maze);
return 0;
}
I dont know really why it's not working at all, any one can instruct/gimme a hint why this code isn't working? I've done all the recursion steps and other method steps for completely finding the path...but unfortunately when compiles appears some errors..!!