TopCoder problem "CubeColoring" used in SRM 484 (Division II Level Three)



Problem Statement

    NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.



Rabbit Taro wants to color the vertices of a cube. He thinks the cube will be beautiful if:
  • Each vertex is colored by a color that is suitable for it.
  • No two adjacent vertices have the same color.




There are N types of colors. You are given a String[] colors. The j-th color is suitable for the i-th vertex if the j-th character of the i-th element of colors is 'Y'. Return the number of different ways to color the cube.
 

Definition

    
Class:CubeColoring
Method:theCount
Parameters:String[]
Returns:long
Method signature:long theCount(String[] colors)
(be sure your method is public)
    
 

Notes

-Two ways are different if there exists an i such that the i-th vertex has a different color in one way than it does in the other way.
 

Constraints

-colors will contain exactly 8 elements.
-Each element in colors will contain between 1 and 32 characters, inclusive.
-Each element in colors will contain the same number of characters.
-Each character in colors will be 'Y' or 'N'.
 

Examples

0)
    
{"Y", "Y", "Y", "Y", "Y", "Y", "Y", "Y"}
Returns: 0
It's impossible to color the cube by only 1 color.
1)
    
{"YNNNNNNN", "NYNNNNNN", "NNYNNNNN", "NNNYNNNN", "NNNNYNNN", "NNNNNYNN", "NNNNNNYN", "NNNNNNNY"}
Returns: 1
Color the i-th vertex by the i-th color.
2)
    
{"YNNYN", "YYYYY", "NYYNY", "YNYYN", "YNNYY", "YNNYY", "NNNYY", "NYYYY"}
Returns: 250
3)
    
{"YNNYN", "YYYYY", "NNNNN", "YNYYN", "YNNYY", "YNNYY", "NNNYY", "NYYYY"}
Returns: 0
No color is suitable for vertex 2.
4)
    
{"YNNYNYYYYYNN", "NNNYNYYNYNNY", "YYNNYYNNNYYN", "YYYYYNNYYYNN", "NNNYYYNNYNYN", "YYYNYYYYNYNN", "NNNNNNYYNYYN", "NNYNYYNNYNYY"}
Returns: 611480

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14237&pm=11130

Writer:

rng_58

Testers:

PabloGilberto , ivan_metelsky , pieguy

Problem categories:

Brute Force, Graph Theory