# maze

unknown
c_cpp
7 months ago
2.8 kB
2
Indexable
Never
```#include <stdio.h>

#define N 7
#define M 7

void printSolution(int sol[N][M], int* solutionCount) {
printf("Tיhe soultion is :\n");
for (int i = 1; i < N - 1; i++) {
for (int j = 1; j < M - 1; j++) {
printf("%d ", sol[i][j]);
}
printf("\n");
}
printf("\n");
(*solutionCount)++;
}

int isSafe(int x, int y, int sol[N][M], int maze[N][M]) {
return maze[x][y] == 0 && sol[x][y] == 0;
}

void solveMazeUtil(int x, int y, int sol[N][M], int maze[N][M], int* solutionCount) {
if (x == N - 2 && y == M - 2) {
sol[x][y] = 1;
printSolution(sol, solutionCount);
sol[x][y] = 0; // Backtrack to find more solutions
return;
}

if (isSafe(x, y, sol, maze)) {
sol[x][y] = 1;

// Explore all four directions
solveMazeUtil(x, y + 1, sol, maze, solutionCount);
solveMazeUtil(x + 1, y, sol, maze, solutionCount);
solveMazeUtil(x, y - 1, sol, maze, solutionCount);
solveMazeUtil(x - 1, y, sol, maze, solutionCount);

sol[x][y] = 0; // Backtrack
}
}

void solveMaze(int maze[N][M]) {
int sol[N][M] = {0};
int solutionCount = 0;

solveMazeUtil(1, 1, sol, maze, &solutionCount);

if (solutionCount == 0) {
printf("No solution found\n");
} else {
printf("Total number of solutions: %d\n", solutionCount);
}
}

int main() {
int maze[N][M] = {
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};

// Maze with no solution
int maze2[N][M] = {
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};

// Maze with one solution
int maze3[N][M] = {
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};

// Another maze with one solution
int maze4[N][M] = {
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};

solveMaze(maze);
printf("\n\n");
solveMaze(maze2);
printf("\n\n");
solveMaze(maze3);
printf("\n\n");
solveMaze(maze4);
return 0;
}
```