Maze Program in C

Queues have many uses. One use of a queue is that it can be used to help find the fastest way out of a maze! The queue is an integral part of a search that is more generally called a Breadth First Search. The idea is as follows. Given a starting point in a maze, travel to all places adjacent to it and mark these as being 1 step away from the start point. Then, for each of these spots that are 1 step away, try travelling to all adjacent spots that are not yet visited. Mark these as 2 spots away. Continue until one of the spots you mark is an exit! By hand, it’s quite easy to visually solve this problem. In order to write a program to do it for a 2D array maze, you need a queue that keeps track of each place you have reached that you haven’t yet tried to visit new places from. The queue is necessary because to get shortest distances, you must process each possible location in the order in which you arrived to them. In addition, as you travel, you should mark which places you’ve reached so far, so that you don’t try to travel to them again. This second part is critical! Without it, you’ll revisit some squares many, many times, resulting in a very slow algorithm. Let’s run through an example by hand, showing what has to happen, visually in code, in both the queue and the 2D array that is storing all shortest distances. We initialize any unvisited square to -1 to indicate that it is in fact, unvisited. When we visit that square, we will update its value to the shortest distance to travel there.