Contents

1 Problem Statement

Please refer to the ascii a-maze problem on this page.

2 Analysis

A maze is a grid of n * m cells. Given a maze, we can detect from a given cell k, which cell you can move to next. This is a defintion of a directed graph. Thus we can model a maze as a directed graph where each cell of the maze is a vertex and its neighbors are the cells you can navigate to from the given cell.

Now the start and end cells are defined as the bottom left and top right cells. Counting the lowest row as 1st row and left most column as 1st column while assuming m rows and n rows in the maze, the start cell is (1,1) while the end cell is (m, n). The problem then becomes of finding the shortest path between the start and end cells.

3 Algorithm

This is the Breadth-First-Search algorithm to find shortest path between two vertexes.

The important piece here will be to transform the ascii maze into the graph and ignoring the cyclic vertexes while finding the shortest path.