Lab 9

Gradescope Starter Code
Due: Monday December 08, 2025 5:00PM
Goals:

Practice working with adjacency lists.
Use breadth-first search to find the shortest path out of a maze.

The main goal for the programming portion of this lab is to compute the shortest path out of a maze. We are assuming that each step has the same cost, so the shortest path can be computed using breadth-first search from the maze entrance to exit locations. In addition to programming, you will also complete some end of semester surveys.

Warning

Although you’ll work on this lab with a partner, you must submit individually. Make sure that both you and your partner have your code at the end of the lab period!

Part 1: Surveys

Part of the lab period is dedicated to filling out the course response forms and the CERP Data Buddies Survey. For each survey, take a screenshot of the submission page, which you’ll submit with this lab. You should save the CERP screenshot if you are enrolled in or may take more CS classes, as other instructors may ask you to do the same thing!

The autograder checks that you submit two image files (with .png or .jpg extensions). This doesn’t actually check the content of the images, so I will check manually and change the grades as necessary, but this should help you remember to submit them.

Once you have finished both surveys, come let me know and grab a sticker! When your partner is also done, you can start working on your code. I’ll be outside of the room until everyone has finished the surveys.

Part 2: Shortest Paths in Mazes

Example Mazes and Adjacency List Format

The maze constructor takes in an adjacency list, an entry point, and an exit point as input. main tests your code using the three mazes shown below:

Maze #1

As an example, the adjacency lists for the Maze #1 will look like this (ordered by the ID of each position):

[1],
[2, 0],
[3, 1],
[7, 2],
...
[15, 13, 10],
[14, 11]

Maze #2

Maze #3

Compute the shortest path between entrance and exit locations.

In the getShortestPath method, use breadth-first search (BFS) to calculate the shortest path between the entrance and exit location of the maze. This method should return a List<Integer> with the nodes in order from entrance to exit (you can use an ArrayList or LinkedList). For the three mazes above, this should be:

4x4 maze: [8, 4, 5, 6, 10, 11, 15]
5x5 maze: [10, 5, 6, 7, 8, 3, 4, 9, 14, 19]
6x6 maze: [18, 12, 6, 7, 8, 9, 15, 21, 27, 33, 34, 35]

The order depends on the fact that adjacencies should be traversed in clockwise order (starting with the right/east direction). As long as you iterate through the adjacencies in the order they are provided in, you should not have a problem, but if you don’t, your output may not match the expected output!

Hint: you can stop the BFS traversal once you reach the exit location. When adding a new (unvisited) location to the queue, keep track of the “parent” of this location (which is the parent in the tree BFS produces). Think carefully about how you can store the parents! The shortest path can then be obtained by starting at the exit and stepping into each parent until we reach the entrance.

Submission

Make sure to submit your screenshots and your code on gradescope. I will check the contents of the screenshots manually, so only use the score for those as a sanity check to confirm you’re submitting everything! As the surveys are individual, this is not set up as group submission and every student must submit.