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.

Enroll in our 5-day mini coding interview class

/* | |

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; | |

} |