PROBLEM STATEMENT
Counting paths can often be a very complex task. Pretend you are in a city,
and you wish to count the number of paths you can take from your current
location to some destination. All roads are one way. To do it all in your
head would cause great damage, so you decide to write a program to solve the
task.
Create a class CityRoads, which contains the method countPaths that takes two
lists, a and b that represent the roads, your starting and destination
locations, from and to, and the length of paths to count. Calculate and return
the total number of distinct paths between your starting and destination
locations of the specified length. Sometimes, the number of distinct paths
cannot be represented by the return type, which causes overflow. If the final
result should be greater than (2^63)-1 or 9223372036854775807, return -1 instead.
DEFINITION
Class: CityRoads
Method: countPaths
Parameters: String[], String[], String, String, int
Returns: long
Method signature (be sure your method is declared public): long
countPaths(String[] a, String[] b, String from, String to, int length);
NOTES
-A road is represented by a[x] and b[x]. It is a one way road from a[x] to b[x].
-There may exist "cycles". A cycle is a road that starts and ends at the same
location.
-The same road may appear more than once. The number of times a specific road
appears in the input is the number of different roads that connect the same two
locations directly.
-It is up to you to detect overflow of the final result. If it occurs, return
-1.
-Note for C++ users: The long data type is a 64-bit signed integer. The long
data type is specific to the gcc compiler.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
-a and b will contain the same number of elements, which will be between 1 and
50, inclusive.
-Each element in a and b contains between 1 and 50 characters, and may only
contain uppercase letters ('A'-'Z' inclusive)
-from and to will be listed in either a or b or both.
-length will be between 1 and 100, inclusive.
EXAMPLES
Example 1:
a={"A","B","A"},
b={"B","C","C"},
from="A", to="C", length=2.
There is one road from 1 to 3 of length 2: it is "A"->"B"->"C". The method
should recognize this as the only path of length 2 that starts at 1 and ends at
3. The method returns 1.
Example 2:
a={"A","A","A","B","B","B","B","C","C","C","D","D","D","E","E","E","E","F","F","
F"},
b={"B","E","D","A","E","F","C","B","D","F","A","C","E","D","A","B","F","E","B","
C"},
from="C", to="D", length=7.
The method returns 739.
Example 3:
a={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"},
b={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"},
from="ABCDEFGHIJKLMNOPQRSTUVWXYZ", to="ABCDEFGHIJKLMNOPQRSTUVWXYZ", length=28.
The method returns 1.
Example 4:
a={"A","B","A","B","A","A","A","A","A","A","A","C","D","E","F","G","H","I"},
b={"A","B","B","A","C","D","E","F","G","H","I","B","B","B","B","B","B","B"},
from="A", to="B", length=14.
The method returns 1824097.
Example 5:
a={"A","A","A","A","A","B","B","B","B","B","A","A","B","B"},
b={"B","B","B","B","B","A","A","A","A","A","A","A","B","B"},
from="A", to="B", length=30.
The method returns -1, because the final result is approximately 1.13*10^25,
which cannot be represented by the return type.
Example 6:
a={"A","B","A","A","A"},
b={"B","A","B","B","B"},
from="A", to="B", length=66.
There are no paths from "A" to "B" of length 66. The method returns 0.