HamiltonPath | Topcoder Archive

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

```
{"NYN",
 "YNN",
 "NNN"}
```
```
Returns: 4
```
The example from the problem statement.
```
{"NYYY",
 "YNNN",
 "YNNN",
 "YNNN"}
```
```
Returns: 0
```
It's impossible to travel all these roads while obeying the other rules.
```
{"NYY",
 "YNY",
 "YYN"}
```
```
Returns: 0
```
This is also impossible.

{"NNNNNY",
 "NNNNYN",
 "NNNNYN",
 "NNNNNN",
 "NYYNNN",
 "YNNNNN"}

Returns: 24

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.