TopCoder problem "HamiltonPath" used in SRM 452 (Division II Level Three)

Problem Statement

    There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.

John plans to travel through the country using the following rules:
  • He must start in one city and end in another city after travelling exactly N-1 roads.
  • He must visit each city exactly once.
  • You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.

Return the number of paths he can choose, modulo 1,000,000,007.


Method signature:int countPaths(String[] roads)
(be sure your method is public)


-roads will contain between 2 and 50 elements, inclusive.
-Each element of roads will contain n characters, where n is the number of elements in roads.
-Each character in roads will be 'Y' or 'N'.
-The i-th character in the i-th element of roads will be 'N'.
-The j-th character in the i-th element of roads and the i-th character in the j-th element of roads will be equal.


Returns: 4
The example from the problem statement.
Returns: 0
It's impossible to travel all these roads while obeying the other rules.
Returns: 0
This is also impossible.
Returns: 24

Problem url:

Problem stats url:




PabloGilberto , connect4 , ivan_metelsky

Problem categories:

Graph Theory, Math