Skip to content

Instantly share code, notes, and snippets.

@charlespunk
Last active December 13, 2015 19:48
Show Gist options
  • Save charlespunk/4965376 to your computer and use it in GitHub Desktop.
Save charlespunk/4965376 to your computer and use it in GitHub Desktop.
Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many
possible paths are there for the robot to go from (0, 0) to (X, Y)?
FOLLOW UP
Imagine certain spots are "off limits", such that the robot cannot step on them. Design an algotithm to find a path for the robot from the
top left to the bottom right.
public static ArrayList<Point> findPath(){
ArrayList<Point> path = new ArrayList<>();
HashSet<Point> deadPoints = new HashSet<>();
if(findPath(0, 0, path, deadPoints)) return path;
else return null;
}
public static boolean findPath(int x, int y, ArrayList<Point> path, HashSet<Point> deadPoints){
Point point = new Point(x, y);
if(point.x == ENDX && point.y == ENDY){
path.add(point);
return true;
}
if(deadPoints.contains(point)) return false;
path.add(point);
if(point.x < ENDX){
boolean rightProbe = findPath(point.x + 1, point.y, path, deadPoints);
if(rightProbe) return true;
}
if(point.y < ENDY){
boolean downProbe = findPath(point.x, point.y + 1, path, deadPoints);
if(downProbe) return true;
}
path.remove(point);
deadPoints.add(point);
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment