Once we model a maze as a graph where each node can have up to 4 edges, we can search for a path in a maze using depth first or breadth first search.
/* | |
Authorship: All credit for the code in this file goes to the authors of the | |
book "Elements of Programming Interviews" by Adnan Aziz, Amit Prakash, and | |
Tsung-Hsien Lee. | |
I have just added explanatory comments, reformatted the code, & changed | |
variable names for understanding. | |
The video to explain this code is here: https://www.youtube.com/watch?v=W9F8fDQj7Ok | |
*/ | |
/* | |
Black cells are walls. We cannot "walk" on them. | |
White cells are traversable. We can "walk" on white cells. | |
*/ | |
public static enum Color { WHITE, BLACK } | |
/* | |
A standard coordinate to represent a cell in the maze with | |
an row and col position. | |
*/ | |
public static class Coordinate { | |
public int row, col; | |
public Coordinate (int row, int col) { | |
this.row = row; | |
this.col = col; | |
} | |
@Override | |
public boolean equals(Object o) { | |
if (this == o) { | |
return true; | |
} | |
if (o == null || getClass() != o.getClass()) { | |
return false; | |
} | |
Coordinate that = (Coordinate) o; | |
if (row != that.row || col != that.col) { | |
return false; | |
} | |
return true; | |
} | |
@Override | |
public int hashCode() { | |
return Objects.hash(row, col); | |
} | |
} | |
/* | |
This is the driver function. It will return the path that we find as | |
a list of Coordinate objects. | |
*/ | |
public static List<Coordinate> searchMaze(List<List<Color>> maze, | |
Coordinate start, Coordinate end) { | |
/* | |
This will hold the path. | |
*/ | |
List<Coordinate> path = new ArrayList<>(); | |
/* | |
Flip the item start position to black. We will start the search | |
from here. | |
Add the coordinate to the start of the path. It is our literal start | |
*/ | |
maze.get(start.row).set(start.col, Color.BLACK); | |
path.add(start); | |
/* | |
If we do not find a path then remove the start node we added to the | |
path and return an empty list down below | |
*/ | |
if (!hasPathToEnd(maze, start, end, path)) { | |
path.remove(path.size() - 1); | |
} | |
/* | |
If we DO find a path, the 'path' variable will have all nodes in the | |
path from start to end, otherwise it will be an empty list | |
*/ | |
return path; | |
} | |
/* | |
A standard DFS for the path that we want to find. | |
*/ | |
private static boolean hasPathToEnd( | |
List<List<Color>> maze, | |
Coordinate node, | |
Coordinate end, | |
List<Coordinate> path | |
) { | |
if (node.equals(end)) { | |
return true; | |
} | |
/* | |
SHIFTS codifies different shifts. | |
Indexes: | |
0 1 | |
{rowDelta, colDelta} | |
*/ | |
final int[][] SHIFTS = { | |
{0 , 1}, // going right | |
{1, 0}, // going down | |
{0, -1}, // going left | |
{-1, 0} // going up` | |
}; | |
/* | |
We: | |
1.) Apply each shift. next is the coordinate that is next to process according | |
to the shift we are on | |
*/ | |
for (int[] shift : SHIFTS) { | |
/* | |
The next item to possibly add to our path and search | |
*/ | |
Coordinate next = new Coordinate(node.row + shift[0], node.col + shift[1]); | |
/* | |
Can this item be walked on? | |
*/ | |
if (canTraverse(next , maze)) { | |
// Yes. Set it to black and add it to the path | |
maze.get(next.row).set(next.col, Color.BLACK); | |
path.add(next); | |
/* | |
Can we finish a path from here now, recurse and find out. If we can | |
we will bubble up the result and this Coordinate will be in the path. | |
*/ | |
if (hasPathToEnd(maze, next, end, path)) { | |
return true; | |
} | |
/* | |
Sadly...things didn't work out, walking from this cell we cannot complete | |
a path. We remove the Coordinate from the path and continue the loop trying | |
to root ourselves at a new "next" position in the path | |
*/ | |
path.remove(path.size() - 1); | |
} | |
} | |
/* | |
No 'next' Coordinates worked from this Coordinate. Return false to our | |
caller. Path not possible, caller will have to keep searching. | |
*/ | |
return false; | |
} | |
/* | |
Validates a given cell, it ensures it is in the maze and is white (can | |
be "walked on") | |
*/ | |
private static boolean canTraverse(Coordinate node, List<List<Color>> maze) { | |
return node.row >= 0 && node.row < maze.size() && | |
node.col >= 0 && node.col < maze.get(node.row).size() && | |
maze.get(node.row).get(node.col) == Color.WHITE; | |
} |