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.
 

Definition

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

Constraints

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

Examples

0)
    
{"NYN",
 "YNN",
 "NNN"}
Returns: 4
The example from the problem statement.
1)
    
{"NYYY",
 "YNNN",
 "YNNN",
 "YNNN"}
Returns: 0
It's impossible to travel all these roads while obeying the other rules.
2)
    
{"NYY",
 "YNY",
 "YYN"}
Returns: 0
This is also impossible.
3)
    
{"NNNNNY",
 "NNNNYN",
 "NNNNYN",
 "NNNNNN",
 "NYYNNN",
 "YNNNNN"}
Returns: 24

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10572

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13906&pm=10572

Writer:

rng_58

Testers:

PabloGilberto , connect4 , ivan_metelsky

Problem categories:

Graph Theory, Math