Maze-Solver Project by Nilesh Yadav

AttainU
AttainU

Maze-Solver

Project description:

A maze in the form of matrix will be given in the form of 1’s and 0’s, where 1 represents the open path and 0 represents the blocked path. - And the goal is to find the path between the source to the destination in the maze (if the path exists) otherwise just return/print -1 indicating no path exists between the source and destination.

Concepts used:

Graphs - Breadth-First-Search Algorithm - Dijkstra’s Algorithm - File Handling

Algorithm for Solving the Problem:

From the given matrix identify the positions, which has 1 and take them as vertices(nodes) of the graph - Then, identify the positions(neighbours) which are immediate left, right, top and bottom, to a given node, if contains 1 . - Whichever neighbour contains 1 for a given node, add that particular node as neighbour to the given node. - Repeat the process until we obtain the entire undirected-unweighted graph. - Now determine if the two nodes (i.e the source-node and the destination-node) connected. - If the two nodes are connected, then determine the path between them (i.e identify the positions) - Finally, print the matrix of the order (which is equal to the order of input) which contains 1 at the positions obtained from the above process and - contains 0 at other positions.

Demo :