Assignment 4: Maze with STL

Objectives

• to use STL containers
• to use STL algorithms

Introduction

A maze with no walls is a rectangular grid containing instructions for how you can move upon entering any space in the grid: S for moving straight through, U for turning around and going back to the previous location, L for turning left and moving one space, and R for turning right and moving one space, or ? for your choice of one of those four options. Note that what adjacent space you move to after proceding "straight", "left", "right", or "turning around", "left" depends on which space you entered from.

There are additional spaces on the board marked with * to indicate a goal (there may be more than one goal in the maze), or with 'X' to indicate a trap that you cannot escape from.

You may enter the maze at any space along its edge and upon entering you are facing away from the edge you just entered (so if you entered from the top you are facing down). The goal is to find a shortest path to any goal that does not exit the maze.

You can use breadth-first-search (BFS) to find a shortest path. BFS starts with a queue of possible starting states, where "state" here is a combination of where you are and your orientation. At each step, BFS takes a state off the front of the queue and adds all the states that can be reached in one move that have not yet been seen (are not in the queue or already taken off the queue), recording the predecessor state for each one added. BFS terminates when taking a goal off the queue, at which point you can construct the solution by following the predecessor links back to the start, or when the queue is empty, in which case there is no solution.

Assignment

Implement a Maze class so that the main function in /c/cs427/hw4/Requried/main.cpp outputs one of the shortest solutions to the maze it reads from standard input. You will have to determine the requirements of the Maze class by inspecting the code in main. The output should consist of one position per line giving the row and then column in the format given in the example, starting with the position off the edge of the board to enter the maze from (using row -1 and column -1 to mean from the top or left respectively) and ending with the position of the goal that was reached. If there are multiple shortest solutions then any one may be output. If there is no solution then there should be no output.

Additional Requirements and Non-Requirements

• your implementation should run in $O(n)$ time, where $n$ is the number of spaces in the grid ($n = w \cdot h$)
• your code should not use any plain arrays
• you should favor using STL algorithms or the range-based for over implementing code that performs the same function or code that explicitly iterates over a collection by directly using indices or iterators
• note that error handling is handled by main and you can assume that the parameter passed to the Maze constructor represents a valid maze (a non-empty rectangle of valid characters)

Example

If simple_4x4.txt contains the maze shown below, then executing Maze should produce the following output.

[jrg94@raven Maze]$ cat simple_4x4.txt
LSUR
?RXR
LS*U
L?RR
[jrg94@raven Maze]$ ./Maze < simple_4x4.txt
(1, -1)
(1, 0)
(2, 0)
(2, 1)
(2, 2)

Submissions

Submit whatever source code (.cpp and .hpp) files you created and a makefile that builds the Maze executable when make is run with no arguments or with target Maze. Your makefile must assume that the main.cpp file is in the current directory; do not hard-code the directory containing that file.