Due: Friday, 4 December 2015
Navigation
A. Shortest Paths
The skeleton contains interface Graph<VLabel, ELabel>
and an implementation
of it, SimpleGraph
, for testing purposes.
The vertices of these graphs are of type Integer
and edges
are essentially (ordered) pairs of Integer
s.
This particular graph API is designed so that the entire graph need not
be in memory (or even in existence) until it is needed. Certain implementations,
in fact, can be (at least conceptually) infinite.
In the source file
Search.java
, implement the method A* search to find a shortest path between
two selected nodes of the graph. There are some things to consider in
adapting the bare algorithm in class to this problem:
- Since you don't necessarily know what all the vertices are, a modification to our algorithm from class is necessary. Rather than filling the fringe (or work queue) with all the vertices, just put in vertices you've seen: initially the starting and ending vertex, and subsequently any vertex that you find at the end of an edge you are processing. When you search for the vertex with lowest estimated distance, you will, of course, not find any of the unprocessed vertices, since they will not be in your fringe structure, but that's OK, since according to the algorithm, their estimated distance to the end vertex will be infinite anyway.
- When you change the distance estimate to a vertex, you will re-order the
fringe. This requires some care. I suggest you use a
TreeSet
to implement your priority queue. SinceTreeSet
assumes that the ordering of items within it remains constant after they are added, you'll need to first delete the vertex from the set, then change its estimated distance, and then re-insert it, in that order. [Thought for the final: be able to explain why this order is necessary.]
B. Counting Paths
[Due to M. Dynin, from a contest in St. Petersburg, Russia] Given a rectangle of letters (such as
AB
BC
), a starting position within that rectangle (such as the character in the
upper-left corner), and a string (such as "ABBC"
), consider the
question of finding paths through the letters that match
the given string, begin at the starting
position, and at each step move one square in one of the eight compass
directions (north, south, east, west, northeast, northwest, southeast,
southwest). For the given example, there are two such paths. They are
({\tt E-SW-E}) and ({\tt S-NE-S})---that is, "one step east, one step
southwest, one step east" and "one step south, one step northeast,
and one step south." For the rectangle
CBB
BBA
and the string "BBCBBA"
, starting at square in the middle of the
top row, there are 12 paths. Paths are allowed to visit the same
position twice.
Using the template in CountPaths.java
,
you are to write a program that, given such a rectangle, string, and
starting position, reports the number of distinct paths that match the
string, according to the definitions above. The input (on the
standard input, System.in
) will consist of
four positive integers (call them M, N, r, and c), a string
(S), and M strings consisting of upper-case letters A-Z,
each of which is N characters long. These inputs are all
separated from each other by whitespace. The M strings are the
rows of the rectangle, from top to bottom. The pair (r,c) gives the
row-column coordinates of the starting position, with 0 <=
r <
M, 0
<=
c <
N.
Row 0 is the top row; column 0 is the left column. The output will be
a line reporting the number of paths in the format shown in the
examples.
You may assume that the number of paths is less than 263 (fits in a
Java long
),
M <=
80, N <=
80. Nevertheless, be aware that the time limit is
only a few seconds.
Example 1:
Input:
2 2 0 0
ABBC AB
BC
Output:
There are 2 paths.
Example 2:
Input:
2 3 0 1 BBCBBA CBB BBA
Output:
There are 12 paths.