Homework 9: Graphs, Etc.

Due: Friday, 4 December 2015

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 Integers.
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:

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.