Vertice removal at end in SearchMaze

**unknown_user** · July 12, 2017, 4:10pm

I am trying to understand the SearchMaze problem and I don’t understand the need of removing the last entry from the path if no path to exist vertex was found which is done here

github.com

adnanaziz/epicode/blob/master/java/src/main/java/com/epi/SearchMaze.java#L81




  final int[][] SHIFT = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  for (int[] s : SHIFT) {
    Coordinate next = new Coordinate(cur.x + s[0], cur.y + s[1]);
    if (isFeasible(next, maze)) {
      maze.get(next.x).set(next.y, Color.BLACK);
      path.add(next);
      if (searchMazeHelper(maze, next, e, path)) {
        return true;
      }
      path.remove(path.size() - 1);
    }
  }
  return false;
}


// Checks cur is within maze and is a white pixel.
private static boolean isFeasible(Coordinate cur, List<List<Color>> maze) {
  return cur.x >= 0 && cur.x < maze.size() && cur.y >= 0
      && cur.y < maze.get(cur.x).size()
      && maze.get(cur.x).get(cur.y) == Color.WHITE;

Why is this needed?

Thanks.

**tsunghsienlee** · July 13, 2017, 3:00am

Since we add an entry always in path.add(next), if we cannot find an path (which will return true), we need to clean that by removing that entry. It is common programming skill used in implementing DFS-like search while having one variable to store the result (i.e., path).

Feel free to let us know if you have any problem.