APCS
Solving Mazes using ArrayLists
Table of Contents
Slide Content
3 Problem Description
4 Algorithm
5 - 7 Explanation of how text maze is converted to an ArrayList
8 - 21 Explanation of the Algorithm
22 - 27 Practice
Problem Description
The program will answer whether or a not a path is available in a maze from a
starting location to an ending location (goal).
Students will write two static methods adjacent and isSolvable
Algorithm - isSolvable( ArrayList<Location> locs )
1. Move the first Location of origList into procList while also removing it from
origList.
2. If the element at the end of origList is removed, return true, as you have
reached the goal
3. Find all Locations in origList that are adjacent to the first Location in
procList and append them to the end of procList while also removing them
from origList.
4. Remove the first point from procList
5. If procList is empty return false, otherwise repeat steps 2 - 4
Grid
The grid is a text file composed of characters. There are only three characters that
are important: space, "$", and "S".
The digits are provided to help you identify
the rows and columns of the maze.
Grid
The program will provide you with an ArrayList of Locations. Spaces are converted
to Locations and put into an ArrayList: The maze below would contain the
following Locations (1,1), (1,2), (1,3), (2,1), (2,2), (2,3)
Grid
The Location represented by the "S", (2,1) is inserted at the beginning of the list
and the Location represented by the "$", (1,3) is added to the end of the list.
S $
(2,1), (1,1), (1,2), (2,2), (2,3), (1,3)
Algorithm
origList: (2,1), (1,1), (1,2), (2,2), (2,3), (1,3)
procList:
1. Move the first point of origList into procList also removing it from origList.
origList: (1,1), (1,2), (2,2), (2,3), (1,3)
procList: (2,1)
Algorithm
origList: (1,1), (1,2), (2,2), (2,3), (1,3)
procList: (2,1)
2. If the element at the end of origList (1,3) is adjacent to the first Location in
procList (2,1) return true, as you have reached the goal
No, (1,3) is not adjacent to (2,1)
Algorithm
origList: (1,1), (1,2), (2,2), (2,3), (1,3)
procList: (2,1)
3. Find all Locations in origList that are adjacent to the first Location in procList
and append them to the end of procList while also removing them from origList.
origList: (1,1), (1,2), (2,2), (2,3), (1,3)
procList: (2,1), (1,1), (2,2)
Algorithm
origList: (1,2), (2,3), (1,3)
procList: (2,1), (1,1), (2,2)
4. Remove the first point from procList
origList: (1,2), (2,3), (1,3)
procList: (1,1), (2,2)
Algorithm
origList: (1,2), (2,3), (1,3)
procList: (1,1), (2,2)
5. If procList is empty return false, otherwise repeat steps 2 - 4
Nope, procList is not empty, so we go back to step 2.
Algorithm
origList: (1,2), (2,3), (1,3)
procList: (1,1), (2,2)
2. If the element at the end of origList (1,3) is adjacent to the first Location in
procList (1,1) return true, as you have reached the goal
No, (1,3) is not adjacent to (1,1)
Algorithm
origList: (1,2), (2,3), (1,3)
procList: (1,1), (2,2)
3. Find all Locations in origList that are adjacent to the first Location in procList
and append them to the end of procList while also removing them from origList.
origList: (1,2), (2,3), (1,3)
procList: (1,1), (2,2), (1,2)
Algorithm
origList: (2,3), (1,3)
procList: (1,1), (2,2), (1,2)
4. Remove the first point from procList
origList: (2,3), (1,3)
procList: (2,2), (1,2)
Algorithm
origList: (2,3), (1,3)
procList: (2,2), (1,2)
5. If procList is empty return false, otherwise repeat steps 2 - 4
Nope, procList is not empty, so we go back to step 2.
Algorithm
origList: (2,3), (1,3)
procList: (2,2), (1,2)
2. If the element at the end of origList (1,3) is adjacent to the first Location in
procList (2,2) return true, as you have reached the goal
Nope, it is not.
Algorithm
origList: (2,3), (1,3)
procList: (2,2), (1,2)
3. Find all Locations in origList that are adjacent to the first Location in procList
and append them to the end of procList while also removing them from origList.
origList: (2,3), (1,3)
procList: (2,2), (1,2), (2,3)
Algorithm
origList: (1,3)
procList: (2,2), (1,2), (2,3)
4. Remove the first point from procList
origList: (1,3)
procList: (1,2), (2,3)
Algorithm
origList: (1,3)
procList: (1,2), (2,3)
5. If procList is empty return false, otherwise repeat steps 2 - 4
Nope, procList is not empty, so we go back to step 2.
Algorithm
origList: (1,3)
procList: (1,2), (2,3)
2. If the element at the end of origList (1,3) is adjacent to the first Location in
procList (1,2) return true, as you have reached the goal
Yes it is, return true!
Quick Check for Understanding
The next slide will check your understanding of converting a maze to Locations.
Grid
The point represented by the "S" is inserted at the beginning of the list and the
point represented by the "$"s added to the end of the list. Write all the points.
S $
_______________________________________
(3,2), (1,2), (2,1), (2,2), (3,1), (4,1), (4,2), (3,2)
Algorithm
origList: (3,2), (1,2), (2,2), (2,3), (3,1), (4,1), (4,2), (1,1)
procList:
1. Move the first point of origList into procList also removing it from origList.
origList:
procList:
Algorithm
origList: (1,2), (2,2), (2,3), (3,1), (4,1), (4,2), (1,1)
procList: (3,2)
2. If the element at the end of origList is adjacent to the first Location in procList
return true, as you have reached the goal
Algorithm
origList: (1,2), (2,2), (2,3), (3,1), (4,1), (4,2), (1,1)
procList: (3,2)
3. Find all Locations in origList that are adjacent to the first Location in procList
and append them to the end of procList while also removing them from origList.
Algorithm
1. Move the first Location of origList into procList while also removing it from
origList.
2. If the element at the end of origList is removed, return true, as you reached
the goal
3. Find all Locations in origList that are adjacent to the first Location in
procList and append them to the end of procList while also removing them
from origList.
4. Remove the first point from procList
5. If procList is empty return false, otherwise repeat steps 2 - 4