JOIN
Get Time

   Problem Statement  

 Problem Statement for GearsDiv1

Problem Statement

    

Goose Tattarrattat has a machine that contains N gears (cogwheels). The gears are numbered 0 through N-1. Each of the gears has one of three colors: red, green, or blue.



Some pairs of gears mesh. Let X and Y be two meshing gears. Note that if X is turning, Y must clearly be turning in the opposite direction (clockwise vs. counter-clockwise). Two gears with the same color never mesh. Apart from that, do not assume anything about the pairs of meshing gears.



You are given a String color and a String[] graph. For each i, character i of color represents the color of gear i: 'R' is red, 'G' is green, and 'B' is blue. The String[] graph contains the information on meshing pairs of gears: If the j-th character of the i-th element of graph is 'Y', gear i meshes with gear j.



We want all gears to turn at the same time. Additionally, all gears of the same color must turn in the same direction. Return the minimal number of gears that have to be removed from the machine in order to achieve this goal.

 

Definition

    
Class:GearsDiv1
Method:getmin
Parameters:String, String[]
Returns:int
Method signature:int getmin(String color, String[] graph)
(be sure your method is public)
    
 

Notes

-Removing a gear creates a gap between the other gears, no new meshing pairs of gears are created by removing a gear.
-The graph described by graph is not necessarily planar.
 

Constraints

-color will contain between 2 and 50 characters, inclusive.
-Each character in color will be 'R' or 'G' or 'B'.
-graph will contain exactly N elements, where N is the number of characters in color.
-Each element of graph will contain exactly N characters, where N is the number of characters in color.
-Each character in graph will be either 'Y' or 'N'.
-For each i, the i-th character of the i-th element of graph will be 'N'.
-For each i and j, the i-th character of the j-th element of graph and the j-th character of the i-th element of graph will be same.
-For each i and j, if the i-th and the j-th character of color are equal, then the i-th character of the j-th element of graph will be 'N'.
 

Examples

0)
    
"RGB"
{"NYY","YNY","YYN"}
Returns: 1
We have three gears, each meshes with each of the others. In this configuration the gears are not able to turn at all. However, as soon as we remove any of the gears, the other two will be able to turn.
1)
    
"RGBR"
{"NNNN","NNNN","NNNN","NNNN"}
Returns: 0
Here, each of the gears can turn without interacting with the others.
2)
    
"RGBR"
{"NYNN","YNYN","NYNY","NNYN"}
Returns: 1
These are four gears arranged into a row. It is possible to turn all these gears at the same time, but the two red gears would turn in opposite directions. Thus we need to remove at least one gear.
3)
    
"RRRRRGRRBGRRGBBGGGBRRRGBRGRRGG"
{"NNNNNYNNNYNNYNNNYNNNNNNNNYNNYY",
 "NNNNNNNNYNNNYNYNNYNNNNYNNYNNYY",
 "NNNNNYNNNNNNNNNNNNYNNNNNNYNNNY",
 "NNNNNNNNNYNNYNNYYYNNNNYNNYNNNN",
 "NNNNNNNNNYNNYNNYYYNNNNYNNNNNNN",
 "YNYNNNYYYNNYNYYNNNNNYYNYNNYYNN",
 "NNNNNYNNNNNNNNNYYYNNNNYNNYNNYY",
 "NNNNNYNNNNNNNNNYNNNNNNNNNNNNYN",
 "NYNNNYNNNYNNYNNYYYNNNNYNNYNNYY",
 "YNNYYNNNYNNNNYYNNNYNYYNYNNNNNN",
 "NNNNNNNNNNNNYNNYNYNNNNYNNNNNNY",
 "NNNNNYNNNNNNYNNYYYNNNNNNNNNNYN",
 "YYNYYNNNYNYYNYYNNNYNYNNYNNNNNN",
 "NNNNNYNNNYNNYNNYYYNNNNYNNYNYYY",
 "NYNNNYNNNYNNYNNYYYNNNNYNNYNNYY",
 "NNNYYNYYYNYYNYYNNNYNYNNYYNYYNN",
 "YNNYYNYNYNNYNYYNNNYNNNNYYNNYNN",
 "NYNYYNYNYNYYNYYNNNNYYNNYYNYNNN",
 "NNYNNNNNNYNNYNNYYNNNNNYNNYNNNY",
 "NNNNNNNNNNNNNNNNNYNNNNYNNYNNNY",
 "NNNNNYNNNYNNYNNYNYNNNNYNNNNNYY",
 "NNNNNYNNNYNNNNNNNNNNNNYNNNNNNN",
 "NYNYYNYNYNYNNYYNNNYYYYNYYNYNNN",
 "NNNNNYNNNYNNYNNYYYNNNNYNNNNNNY",
 "NNNNNNNNNNNNNNNYYYNNNNYNNYNNYY",
 "YYYYNNYNYNNNNYYNNNYYNNNNYNYYNN",
 "NNNNNYNNNNNNNNNYNYNNNNYNNYNNYN",
 "NNNNNYNNNNNNNYNYYNNNNNNNNYNNYY",
 "YYNNNNYYYNNYNYYNNNNNYNNNYNYYNN",
 "YYYNNNYNYNYNNYYNNNYYYNNYYNNYNN"}
Returns: 3

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 589 Round 1 - Division I, Level Two