Other 2006 FR Questions FR other years Be Prepared Home
AB-4
Part (a)
  // returns true if the specified locations are possible
  // starting and ending locations for an NE-path
  // otherwise, returns false
  private boolean possibleEnds(Location start, Location end)
  {
    return theEnv.isEmpty(start) && theEnv.isEmpty(end) &&
            start.row() >= end.row() && start.col() <= end.col();
  }

Part (b)
  // returns a list containing a sequence of empty locations
  // that form an NE-path from start to end;
  // returns null if no such path exists
  // postcondition:  theEnv is unchanged
  public List<Location> findNEPath(Location start, Location end)
  {
    if (!possibleEnds(start, end))
      return null;

    List<Location> path; 1

    if (start.equals(end))
    {
      path = new LinkedList<Location>(); 2
      path.add(start); 3
      return path;
    }

    path = findNEPath(theEnv.getNeighbor(start, Direction.NORTH), end);
    if (path == null)
      path = findNEPath(theEnv.getNeighbor(start, Direction.EAST), end);

    if (path != null)
      path.add(0, start); 4

    return path;
  }
}
Notes:
  1. We declared it as List, not as LinkedList or ArrayList, because findNEPath returns a List.

  2. A LinkedList is more appropriate here than an ArrayList, because we plan to insert values at the beginning many times.  However, you would receive full credit with an ArrayList.

  3. Or
    path.add(end);
  4. Or
      ((LinkedList<Location>)path).addFirst(start);

Other 2006 FR Questions | Back to Contents

Copyright © 2006 by Skylight Publishing
support@skylit.com