maze processing

While going through past ACM problems, you may have noticed how frequently mazes find their way into the problem set. For example, problem G in 2000 (greater NY region), or problem 6, 2000 (Central America), or even problem C 1999 world finals.

The underlying idea in all these problems is maze traversal, and in this page we'll discuss some techniques used for it.

Backtracking :
       while(currentCell != endCell)
         { set currentCell = visited;
            for all neighboringCells {
              if(neighboringCell != visited) stack.push(neighboringCell); }
            currentCell = stack.top(); stack.pop();
                        }

This is the basic idea. Keep going till you reach a dead end, and continue from the last unvisited passage. We must include some error correction, (when stack is empty, we are doomed). Here is an applet that shows how the stack looks like when we are finding our way.

To find the shortest path, we can either keep a note of all paths explored, and then sort them to get a shortest path; or we can use some algorithms like Dijkstra's shortest path algorithm.

home

Our Teams

2002

2001

2000