SnowStorm | Topcoder Archive

Problem Statement

Last night in Eskimo village it snowed heavily, so all the paths between the different igloos have been covered with snow. The mayor wants to help keep the community together and clean up the snow so that you can reach every igloo from all other igloos.

You are given a String[] paths, where character j of element i is 'Y' if there's a path between the ith igloo and the jth igloo, or 'N' otherwise. All paths are bidirectional. Determine the number of different sets of paths that can be cleaned to achieve the mayor's goal, and return this number modulo 10,000.

Definition

Class:: SnowStorm
Method:: countWays
Parameters:: String[]
Returns:: int
Method signature:: int countWays(String[] paths)
(be sure your method is public)

Constraints

paths must have between 1 and 15 elements, inclusive.
Each element of paths must have exactly n characters, where n is the number of elements of paths.
Each character in paths must be either 'Y' or 'N'.
Character i of element i of paths will always be 'N'.
Character j in row i of paths will be equal to character i in row j of paths.

Examples

```
{
 "NYY",
 "YNY",
 "YYN"}
```
```
Returns: 4
```
There are 4 different snow clearing possibilities: - clear the paths 1-2 and 2-3. - clear the paths 1-3 and 2-3. - clear the paths 1-3 and 1-2. - or clear the paths 1-2, 1-3, 2-3.
```
{
 "NYNN",
 "YNYY",
 "NYNN",
 "NYNN"}
```
```
Returns: 1
```
To be able to get from every igloo to any other igloo, we must clear all the paths. So the number of solutions is 1.

{
 "NYYY",
 "YNYY",
 "YYNY",
 "YYYN"}

Returns: 38

```
{
 "NN",
 "NN"}
```
```
Returns: 0
```
There are no paths to be cleaned, and you can't reach igloo 2 from igloo 1, so the number of solutions is 0.

{ "NYYYNYYYYYNYYYY",
 "YNYYYYYYYNNYYYY",
 "YYNYYNYYNYYYYYY",
 "YYYNYYYYYYNNNYN",
 "NYYYNNYYYYYYYYY",
 "YYNYNNYYYYYYYYY",
 "YYYYYYNYYYYYYYY",
 "YYYYYYYNYNYYYYY",
 "YYNYYYYYNYNYYYY",
 "YNYYYYYNYNYYYYY",
 "NNYNYYYYNYNYYYY",
 "YYYNYYYYYYYNYYY",
 "YYYNYYYYYYYYNNY",
 "YYYYYYYYYYYYNNY",
 "YYYNYYYYYYYYYYN"}

Returns: 2704

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.