BFS Implementation
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ROWS 6
#define COLS 6
// Structure to store 2D coordinates
typedef struct {
int r;
int c;
} Point;
// Queue node representation for BFS
typedef struct {
Point data[ROWS * COLS];
int front;
int rear;
} Queue;
// Queue utility functions
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
bool isEmpty(Queue *q) {
return q->front == q->rear;
void enqueue(Queue *q, Point p) {
q->data[q->rear++] = p;
Point dequeue(Queue *q) {
return q->data[q->front++];
// Check if a cell move is valid
bool isValid(int r, int c, char maze[ROWS][COLS], bool visited[ROWS][COLS]) {
return (r >= 0 && r < ROWS && c >= 0 && c < COLS &&
maze[r][c] != '#' && !visited[r][c]);
// BFS Maze Solver Function
bool solveMaze(char maze[ROWS][COLS], Point start, Point finish) {
bool visited[ROWS][COLS] = {false};
Point parent[ROWS][COLS];
// Initialize parent tracking map with invalid markers (-1, -1)
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
parent[i][j] = (Point){-1, -1};
Queue q;
initQueue(&q);
// Enqueue the start coordinate
enqueue(&q, start);
visited[start.r][start.c] = true;
// Movement vectors: Up, Down, Left, Right
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
bool pathFound = false;
while (!isEmpty(&q)) {
Point curr = dequeue(&q);
// If the finish is reached, break early
if (curr.r == finish.r && curr.c == finish.c) {
pathFound = true;
break;
// Explore all 4 orthogonal directions
for (int i = 0; i < 4; i++) {
int nextR = curr.r + dr[i];
int nextC = curr.c + dc[i];
if (isValid(nextR, nextC, maze, visited)) {
visited[nextR][nextC] = true;
parent[nextR][nextC] = curr; // Save path predecessor
enqueue(&q, (Point){nextR, nextC});
// Reconstruct and draw the shortest path if an exit was discovered
if (pathFound) {
Point curr = parent[finish.r][finish.c];
while (curr.r != start.r || curr.c != start.c) {
maze[curr.r][curr.c] = '*'; // Mark shortest path
curr = parent[curr.r][curr.c];
return true;
return false;
int main() {
// '#' = Wall, '.' = Open Path, 'S' = Start, 'F' = Finish
char maze[ROWS][COLS] = {
{'S', '.', '#', '#', '#', '#'},
{'.', '.', '.', '.', '.', '#'},
{'#', '.', '#', '#', '.', '#'},
{'#', '.', '.', '#', '.', '.'},
{'#', '#', '.', '#', '#', '.'},
{'#', '#', '.', '.', '.', 'F'}
};
Point start = {0, 0};
Point finish = {5, 5};
printf("Original Maze:\n");
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
printf("%c ", maze[i][j]);
printf("\n");
if (solveMaze(maze, start, finish)) {
printf("\nMaze Solved (Shortest path marked with *):\n");
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
printf("%c ", maze[i][j]);
printf("\n");
}
} else {
printf("\nNo clear path exists to exit the maze.\n");
return 0;