TopCoder problem "SnowStorm" used in TCCC06 Round 1C (Division I Level Three)



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

0)
    
{
 "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.

1)
    
{
 "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.
2)
    
{
 "NYYY",
 "YNYY",
 "YYNY",
 "YYYN"}
Returns: 38
3)
    
{
 "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.
4)
    
{ "NYYYNYYYYYNYYYY",
 "YNYYYYYYYNNYYYY",
 "YYNYYNYYNYYYYYY",
 "YYYNYYYYYYNNNYN",
 "NYYYNNYYYYYYYYY",
 "YYNYNNYYYYYYYYY",
 "YYYYYYNYYYYYYYY",
 "YYYYYYYNYNYYYYY",
 "YYNYYYYYNYNYYYY",
 "YNYYYYYNYNYYYYY",
 "NNYNYYYYNYNYYYY",
 "YYYNYYYYYYYNYYY",
 "YYYNYYYYYYYYNNY",
 "YYYYYYYYYYYYNNY",
 "YYYNYYYYYYYYYYN"}

Returns: 2704

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10104&pm=6695

Writer:

Cosmin.ro

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

Problem categories:

Brute Force, Dynamic Programming