Search a maze
Search_maze.cpp SearchMaze.javapublic static LinkedList<Coordinate> searchMaze(int[][] maze, Coordinate s,
Coordinate e) {
LinkedList<Coordinate> path = new LinkedList<>();
maze[s.x][s.y] = 1;
path.addFirst(s);
if (!searchMazeHelper(maze, s, e, path)) {
path.removeLast();
}
return path; // empty path means no path between s and e.
}
// Performs DFS to find a feasible path.
private static boolean searchMazeHelper(int[][] maze, Coordinate cur,
Coordinate e,
LinkedList<Coordinate> path) {
if (cur.equals(e)) {
return true;
}
List<? extends List<Integer>> shift = Arrays.asList(Arrays.asList(0, 1),
Arrays.asList(0, -1), Arrays.asList(1, 0), Arrays.asList(-1, 0));
for (List<Integer> s : shift) {
Coordinate next = new Coordinate(cur.x + s.get(0), cur.y + s.get(1));
if (isFeasible(next, maze)) {
maze[next.x][next.y] = 1;
path.addLast(next);
if (searchMazeHelper(maze, next, e, path)) {
return true;
}
path.removeLast();
}
}
return false;
}
// Checks cur is within maze and is a white pixel.
private static boolean isFeasible(Coordinate cur, int[][] maze) {
return cur.x >= 0 && cur.x < maze.length && cur.y >= 0
&& cur.y < maze[cur.x].length && maze[cur.x][cur.y] == 0;
}
public static class Coordinate {
public int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Coordinate that = (Coordinate) o;
if (x != that.x) {
return false;
}
if (y != that.y) {
return false;
}
return true;
}
public String toString() {
return x + " " + y;
}
}
