Last active
December 13, 2015 19:48
-
-
Save charlespunk/4965376 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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