shakazulu
BAN USER//starting at (0,0), and can only move in positive (dx,dy) movements, get the path that gets most coins
public List<Point> GetPathWithMostCoins(Set<Point> coinsList)
{
List<Point> emptyPath = new ArrayList<>();
return GetPathWithMostCoinsRec(emptyPath, new ArrayList<Point>(coinsList), new Point(0,0), emptyPath);
}
public List<Point> GetPathWithMostCoinsRec(List<Point> currentPath, List<Point> currPossibilities, Point currPoint, List<Point> currLongest)
{
if (currPossibilities.isEmpty())
{
if (currLongest.size() < currentPath.size())
{
currLongest = currentPath;
}
return currLongest;
}
for (Point nextStep : currPossibilities)
{
List<Point> pathContinued = new ArrayList<>();
for (Point p : currentPath)
{
pathContinued.add(p);
}
pathContinued.add(nextStep);
List<Point> longestPathMaybe = GetPathWithMostCoinsRec(pathContinued, getNextXPossibiliteisList(nextStep, currPossibilities), nextStep, currLongest);
if (currLongest.size() < longestPathMaybe.size())
{
currLongest = longestPathMaybe;
}
}
return currLongest;
}
private List<Point> getNextXPossibiliteisList(Point minPoint, List<Point> currList)
{
List<Point> result = new ArrayList<Point>();
for (Point point : currList)
{
if (point.getX() >= minPoint.getX() && point.getY() >= minPoint.getY() && !point.equals(minPoint))
{
result.add(point);
}
}
return result;
}
- shakazulu April 16, 2018