Scribd
Upload
28 views4 pages

Maze Prob

The maze problem involves finding a path in a grid-like structure using algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS). The maze is represented as a 2D array where 0s are walls and 1s are paths, and the algorithms utilize recursion, stacks, or queues to explore the maze. A sample C program demonstrates the DFS approach to find a path from a starting point to a destination in the maze.

Uploaded by

kunalbajaj0911
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
28 views4 pages

Maze Prob

The maze problem involves finding a path in a grid-like structure using algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS). The maze is represented as a 2D array where 0s are walls and 1s are paths, and the algorithms utilize recursion, stacks, or queues to explore the maze. A sample C program demonstrates the DFS approach to find a path from a starting point to a destination in the maze.

Uploaded by

kunalbajaj0911
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

The maze problem in data structures, particularly using C, involves finding a path from a starting

point to a destination in a grid-like structure (maze) where some cells are blocked. Algorithms
like Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to solve this, often
utilizing recursion and stacks. A common approach is to represent the maze as a 2D array
(matrix) where 0s represent walls and 1s represent traversable paths.

. Representing the Maze:

 2D Array: The maze is typically represented as a 2D array (matrix) where each cell
contains a value indicating whether it's a wall (0) or a path (1).

Algorithms for Solving the Maze:

 Depth-First Search (DFS):

 Recursion: DFS explores the maze by recursively visiting adjacent cells, marking
them as visited to avoid cycles.

 Stack (Optional): DFS can be implemented with a stack to keep track of visited
cells and paths, especially when backtracking is needed.

 Backtracking: If a dead end is reached, the algorithm backtracks to the previous


cell and tries a different path.

 Breadth-First Search (BFS):

 Queue: BFS uses a queue to explore the maze level by level, ensuring the
shortest path is found first.

 Efficiency: BFS is generally preferred when finding the shortest path is a primary
concern.

(-1, 0) - North

(-1, 1) - North-East

( 0, 1) - East

( 1, 1) - South-East

( 1, 0) - South
( 1, -1) - South-West

( 0, -1) - West

(-1, -1) - North-West

Maze problem Program:

#include <stdio.h>

#define ROW 5

#define COL 5

int maze[ROW][COL] = {

{1, 0, 1, 1, 1},

{1, 1, 1, 0, 1},

{0, 0, 1, 1, 1},

{1, 1, 0, 0, 1},

{1, 1, 1, 1, 1}

};

int visited[ROW][COL];

// Directions: N, NE, E, SE, S, SW, W, NW

int dRow[] = {-1, -1, 0, 1, 1, 1, 0, -1};

int dCol[] = { 0, 1, 1, 1, 0, -1, -1, -1};

int isSafe(int row, int col) {

return (row >= 0 && col >= 0 && row < ROW && col < COL &&

maze[row][col] == 1 && visited[row][col] == 0);


}

int dfs(int row, int col, int endRow, int endCol) {

if (row == endRow && col == endCol) {

printf("(%d, %d)\n", row, col);

return 1;

visited[row][col] = 1;

for (int dir = 0; dir < 8; dir++) {

int newRow = row + dRow[dir];

int newCol = col + dCol[dir];

if (isSafe(newRow, newCol)) {

if (dfs(newRow, newCol, endRow, endCol)) {

printf("(%d, %d)\n", row, col); // Backtracking path

return 1;

return 0;

int main() {
int startRow = 0, startCol = 0;

int endRow = 4, endCol = 4;

printf("Path from start to end:\n");

if (!dfs(startRow, startCol, endRow, endCol)) {

printf("No path found!\n");

return 0;

Output:

(4, 4)

(3, 4)

(2, 4)

(2, 3)

(1, 2)

(1, 1)

(1, 0)

(0, 0)

You might also like