Statistics

Problem Statement for "SnowStorm"

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

  1. { "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.

  2. { "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.

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

    Returns: 38

  4. { "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.

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

    Returns: 2704

  6. { "NYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYY", "YYNYYYYYYYYYYYY", "YYYNYYYYYYYYYYY", "YYYYNYYYYYYYYYY", "YYYYYNYYYYYYYYY", "YYYYYYNYYYYYYYY", "YYYYYYYNYYYYYYY", "YYYYYYYYNYYYYYY", "YYYYYYYYYNYYYYY", "YYYYYYYYYYNYYYY", "YYYYYYYYYYYNYYY", "YYYYYYYYYYYYNYY", "YYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYN" }

    Returns: 4896

  7. {"NNYYNN", "NNYNNN", "YYNNNN", "YNNNNY", "NNNNNY", "NNNYYN"}

    Returns: 1

  8. {"N"}

    Returns: 1

  9. {"NY", "YN"}

    Returns: 1

  10. { "NYY", "YNN", "YNN"}

    Returns: 1

  11. { "NNY", "NNY", "YYN"}

    Returns: 1

  12. { "NYY", "YNY", "YYN"}

    Returns: 4

  13. { "NYNN", "YNNN", "NNNY", "NNYN"}

    Returns: 0

  14. { "NNYY", "NNYN", "YYNY", "YNYN"}

    Returns: 4

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

    Returns: 38

  16. { "NNNNY", "NNYYY", "NYNNN", "NYNNN", "YYNNN"}

    Returns: 1

  17. { "NYYYY", "YNNYY", "YNNNN", "YYNNY", "YYNYN"}

    Returns: 38

  18. { "NYYYY", "YNYYY", "YYNYY", "YYYNY", "YYYYN"}

    Returns: 728

  19. { "NYNNNY", "YNNNNY", "NNNYYN", "NNYNNY", "NNYNNY", "YYNYYN"}

    Returns: 20

  20. { "NNYYNN", "NNYYNN", "YYNNYY", "YYNNYY", "NNYYNY", "NNYYYN"}

    Returns: 176

  21. { "NYYYYY", "YNYYYY", "YYNYYY", "YYYNYY", "YYYYNY", "YYYYYN"}

    Returns: 6704

  22. { "NYNNNNY", "YNYNNYN", "NYNNYNY", "NNNNNNN", "NNYNNYY", "NYNNYNN", "YNYNYNN"}

    Returns: 0

  23. { "NYNNYNY", "YNNYNNN", "NNNNYNY", "NYNNYNY", "YNYYNYY", "NNNNYNN", "YNYYYNN"}

    Returns: 170

  24. { "NYYYYYY", "YNYYYYY", "YYNYYYY", "YYYNYYY", "YYYYNYY", "YYYYYNY", "YYYYYYN"}

    Returns: 6256

  25. { "NYNNYNNN", "YNNYYYYN", "NNNYNYNN", "NYYNNYYN", "YYNNNNNN", "NYYYNNYN", "NYNYNYNY", "NNNNNNYN"}

    Returns: 496

  26. { "NYYNYNYN", "YNYNYYYY", "YYNYYYYN", "NNYNYYYY", "YYYYNYYN", "NYYYYNNY", "YYYYYNNY", "NYNYNYYN"}

    Returns: 9064

  27. { "NYYYYYYY", "YNYYYYYY", "YYNYYYYY", "YYYNYYYY", "YYYYNYYY", "YYYYYNYY", "YYYYYYNY", "YYYYYYYN"}

    Returns: 8592

  28. { "NYYNYNYNN", "YNYNNYYYN", "YYNNNYNNY", "NNNNYNNNN", "YNNYNNNNY", "NYYNNNNNN", "YYNNNNNNY", "NYNNNNNNY", "NNYNYNYYN"}

    Returns: 2052

  29. { "NNNYNYNYY", "NNYYYYYNY", "NYNYYYNNN", "YYYNYYNYN", "NYYYNYNNN", "YYYYYNNYN", "NYNNNNNYN", "YNNYNYYNY", "YYNNNNNYN"}

    Returns: 8800

  30. { "NYYYNYYYY", "YNYYYYYYY", "YYNYYYYYY", "YYYNYYYYY", "NYYYNYYYY", "YYYYYNYYY", "YYYYYYNYY", "YYYYYYYNY", "YYYYYYYYN"}

    Returns: 1776

  31. { "NYNYNYYYNN", "YNNYYNYNYY", "NNNNNNNNNY", "YYNNNNNNNY", "NYNNNYYNNN", "YNNNYNNYYN", "YYNNYNNYYN", "YNNNNYYNYN", "NYNNNYYYNN", "NYYYNNNNNN"}

    Returns: 9812

  32. { "NNYYYYYYYY", "NNYYYNYYYN", "YYNYYNNYYN", "YYYNYYNYYY", "YYYYNYNNNN", "YNNYYNNYYY", "YYNNNNNYYY", "YYYYNYYNNN", "YYYYNYYNNY", "YNNYNYYNYN"}

    Returns: 6824

  33. { "NYYYYYYYYY", "YNYYYYYYYY", "YYNYYYYYYY", "YYYNYYYYYY", "YYYYNYYNYY", "YYYYYNYYYY", "YYYYYYNYYY", "YYYYNYYNYY", "YYYYYYYYNY", "YYYYYYYYYN"}

    Returns: 1376

  34. { "NYYNNNYYNNN", "YNYNNYNNNNN", "YYNNYNYNNNN", "NNNNNNYNNNN", "NNYNNYNNYNN", "NYNNYNNYYNN", "YNYYNNNNNNY", "YNNNNYNNYNN", "NNNNYYNYNYY", "NNNNNNNNYNY", "NNNNNNYNYYN"}

    Returns: 9816

  35. { "NNYNYNYYYNY", "NNNNNYNNNYY", "YNNNYYYNYNY", "NNNNNYYNYYN", "YNYNNNNNYNY", "NYYYNNYNNYY", "YNYYNYNNYYN", "YNNNNNNNYNY", "YNYYYNYYNYY", "NYNYNYYNYNY", "YYYNYYNYYYN"}

    Returns: 9880

  36. { "NYYYYYYYYYY", "YNYYYYYYYYY", "YYNYYYYYYYY", "YYYNYYYYYYY", "YYYYNYYYYYY", "YYYYYNYYYYY", "YYYYYYNYYYY", "YYYYYYYNYYY", "YYYYYYYYNYY", "YYYYYYYYYNY", "YYYYYYYYYYN"}

    Returns: 3344

  37. { "NNNNNYNYNNNY", "NNNNNNNYNYYY", "NNNYNYNNYYNN", "NNYNYNNNNNNY", "NNNYNYNYNYNY", "YNYNYNNYNYNY", "NNNNNNNYNYNY", "YYNNYYYNNNNY", "NNYNNNNNNNYY", "NYYNYYYNNNYY", "NYNNNNNNYYNN", "YYNYYYYYYYNN"}

    Returns: 2900

  38. { "NYNYYNYYNYNY", "YNNYYYYNYYYY", "NNNNYNYNNYYN", "YYNNYYYYYNYY", "YYYYNYYNYYYY", "NYNYYNYNNNYY", "YYYYYYNNNYNY", "YNNYNNNNYYNN", "NYNYYNNYNNYY", "YYYNYNYYNNNY", "NYYYYYNNYNNN", "YYNYYYYNYYNN"}

    Returns: 6400

  39. { "NYYYYYYYYYYY", "YNYYYYYYYYYY", "YYNYYYYYYYYY", "YYYNYYYYYYNY", "YYYYNYYYYYYY", "YYYYYNYYYYYY", "YYYYYYNYYYYY", "YYYYYYYNYYYY", "YYYYYYYYNYYY", "YYYYYYYYYNYY", "YYYNYYYYYYNY", "YYYYYYYYYYYN"}

    Returns: 4224

  40. { "NNNNNYNYYNNYN", "NNYNYYNNYNNNY", "NYNNYYYNYNYNY", "NNNNYNYYNYYYN", "NYYYNYNNNNYNY", "YYYNYNNNNYNYY", "NNYYNNNNYNYNY", "YNNYNNNNNYNNY", "YYYNNNYNNNNYN", "NNNYNYNYNNNNY", "NNYYYNYNNNNYN", "YNNYNYNNYNYNN", "NYYNYYYYNYNNN"}

    Returns: 5504

  41. { "NYNYYYYYNYYNN", "YNYNNNYYYYNYN", "NYNYYNNYNNNNN", "YNYNYYYYYNYYY", "YNYYNYYYYYNYY", "YNNYYNYNNNYYN", "YYNYYYNYYNYNN", "YYYYYNYNNYYNY", "NYNYYNYNNNYYY", "YYNNYNNYNNNNN", "YNNYNYYYYNNYN", "NYNYYYNNYNYNN", "NNNYYNNYYNNNN"}

    Returns: 5524

  42. { "NYYYYYNYYYYYY", "YNYYYYNYYYYYY", "YYNYYYYYYYYYY", "YYYNYYYYYYYYY", "YYYYNYYYYYYYY", "YYYYYNYYYYYYY", "NNYYYYNYYYYYY", "YYYYYYYNYYNYY", "YYYYYYYYNYYYY", "YYYYYYYYYNYYY", "YYYYYYYNYYNYY", "YYYYYYYYYYYNY", "YYYYYYYYYYYYN"}

    Returns: 8288

  43. { "NNNNYYYNYNYNNN", "NNNYYYNYYNNNNN", "NNNNYYNYYNNYNN", "NYNNNNNYYNYNYY", "YYYNNNNYNYNNNY", "YYYNNNNYNYNYNY", "YNNNNNNYYNNNNN", "NYYYYYYNYNYNNN", "YYYYNNYYNNYYYN", "NNNNYYNNNNYNNN", "YNNYNNNYYYNYYY", "NNYNNYNNYNYNNY", "NNNYNNNNYNYNNN", "NNNYYYNNNNYYNN"}

    Returns: 2664

  44. { "NYYYNNYNYNYNYN", "YNYYYNYYYYYYNY", "YYNYYYYNNYYNYY", "YYYNYNNYNYNYYY", "NYYYNNYNNYYYNY", "NNYNNNNNYYNNYN", "YYYNYNNNNYNYYY", "NYNYNNNNYNYNYY", "YYNNNYNYNYYYYN", "NYYYYYYNYNYYYY", "YYYNYNNYYYNNNN", "NYNYYNYNYYNNNY", "YNYYNYYYYYNNNY", "NYYYYNYYNYNYYN"}

    Returns: 2784

  45. { "NYYYYYYYYYYYYY", "YNYYYYYYYYYYYY", "YYNYYYYYYYYYYY", "YYYNYYYYYYYYYY", "YYYYNYYYYYYYYY", "YYYYYNYYYYYYYY", "YYYYYYNYYYYYYY", "YYYYYYYNYYYYYY", "YYYYYYYYNYYYYY", "YYYYYYYYYNYYYY", "YYYYYYYYYYNYYY", "YYYYYYYYYYYNYY", "YYYYYYYYYYYYNY", "YYYYYYYYYYYYYN"}

    Returns: 1264

  46. { "NYYNYNYNNYNNYYY", "YNYYNNNNYNNNYYN", "YYNYNNYNNYYNYNN", "NYYNYYNNNYNNNNY", "YNNYNNNNYYNNNNN", "NNNYNNNYNNYNNNY", "YNYNNNNYNNYNYYY", "NNNNNYYNNYYNYYN", "NYNNYNNNNNYNNNN", "YNYYYNNYNNNNNYY", "NNYNNYYYYNNNNNN", "NNNNNNNNNNNNYYN", "YYYNNNYYNNNYNNY", "YYNNNNYYNYNYNNY", "YNNYNYYNNYNNYYN"}

    Returns: 7540

  47. { "NNNYYYYYNYNNNNY", "NNYYNYYNNYYNYYY", "NYNNYYYNYYNYNYY", "YYNNYYYYYNYNYYN", "YNYYNYYYYNYNNYY", "YYYYYNYYYNYYYYY", "YYYYYYNYYYNYYYY", "YNNYYYYNNYYNYYN", "NNYYYYYNNYYNYYY", "YYYNNNYYYNYNYYN", "NYNYYYNYYYNYYYY", "NNYNNYYNNNYNNNN", "NYNYNYYYYYYNNNN", "NYYYYYYYYYYNNNN", "YYYNYYYNYNYNNNN"}

    Returns: 7424

  48. { "NYYYYYYYYYYYYYY", "YNNYNYYYYYYYYYY", "YNNYYYYYYYYYYYY", "YYYNYYYNYYYYYYY", "YNYYNYYYYYYYYYY", "YYYYYNYYYYNYYYY", "YYYYYYNYYYYYYYY", "YYYNYYYNYYYYYYY", "YYYYYYYYNYYYYYY", "YYYYYYYYYNYYYYN", "YYYYYNYYYYNYYYY", "YYYYYYYYYYYNYYY", "YYYYYYYYYYYYNYY", "YYYYYYYYYYYYYNY", "YYYYYYYYYNYYYYN"}

    Returns: 432

  49. { "NYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYY", "YYNYYYYYYYYYYYY", "YYYNYYYYYYYYYYY", "YYYYNYYYYYYYYYY", "YYYYYNYYYYYYYYY", "YYYYYYNYYYYYYYY", "YYYYYYYNYYYYYYY", "YYYYYYYYNYYYYYY", "YYYYYYYYYNYYYYY", "YYYYYYYYYYNYYYY", "YYYYYYYYYYYNYYY", "YYYYYYYYYYYYNYY", "YYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYN"}

    Returns: 4896

  50. { "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNN"}

    Returns: 0

  51. { "NYYYYYYYYYYYYYN", "YNYYYYYYYYYYYYN", "YYNYYYYYYYYYYYN", "YYYNYYYYYYYYYYN", "YYYYNYYYYYYYYYN", "YYYYYNYYYYYYYYN", "YYYYYYNYYYYYYYN", "YYYYYYYNYYYYYYN", "YYYYYYYYNYYYYYN", "YYYYYYYYYNYYYYN", "YYYYYYYYYYNYYYN", "YYYYYYYYYYYNYYN", "YYYYYYYYYYYYNYN", "YYYYYYYYYYYYYNN", "NNNNNNNNNNNNNNN" }

    Returns: 0

  52. {"NYYYNYYYYYYY", "YNYNYYYYYYYY", "YYNYYYYYYYYY", "YNYNYYYYYYYY", "NYYYNYYYYYYY", "YYYYYNYYYYYY", "YYYYYYNYYYYY", "YYYYYYYNYYYY", "YYYYYYYYNYYY", "YYYYYYYYYNYY", "YYYYYYYYYYNY", "YYYYYYYYYYYN" }

    Returns: 6112

  53. {"NYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYY", "YYNYYYYYYYYYYYY", "YYYNYYYYYYYYYYY", "YYYYNYYYYYYYYYY", "YYYYYNYYYYYYYYY", "YYYYYYNYYYYYYYY", "YYYYYYYNYYYYYYY", "YYYYYYYYNYYYYYY", "YYYYYYYYYNYYYYY", "YYYYYYYYYYNYYYY", "YYYYYYYYYYYNYYY", "YYYYYYYYYYYYNYY", "YYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYN" }

    Returns: 4896

  54. {"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.
This problem was used for: