JOIN
Get Time

   Problem Statement  

 Problem Statement for Rumor

Problem Statement

    There are N rabbits who like to gossip. They are numbered from 0 to N-1.

There are two rumors. Let's call them A and B. At this moment, each rabbit either knows both rumors or no rumors at all. The rabbits want to spread the rumors to everyone as quickly as possible.

Rabbits are very picky when it comes to spreading rumors. Each rabbit only trusts some of the other rabbits. Moreover, the situation is not necessarily symmetric - there may be rabbits A and B such that A trusts B, but B does not trust A.

At the beginning of each day, each rabbit who knows at least one rumor chooses a rumor X it knows. The rabbit then spends the day spreading rumor X. A rabbit will learn a new rumor if it is spreaded by someone it trusts. Note that a rabbit may learn both rumors in the same day (from two different other rabbits). Also note that a rabbit may spread one rumor and learn the other rumor on the same day.

You are given a String knowledge and a String[] graph. The String knowledge has exactly N characters. Character i of knowledge is 'Y' if rabbit i already knows both rumors, or 'N' if it does not know the rumors yet. The String[] graph contains N strings with N characters each. Element i of graph describes rabbits who trust rabbit i: character j of element i of graph is 'Y' if rabbit j trusts rabbit i, or 'N' if rabbit j does not trust rabbit i. In other words, graph[i][j] is 'Y' if and only if rabbit i will spread rumors to rabbit j.

Return the minimum number of days needed to spread both rumors so that each of the N rabbits will know both rumors. If it is impossible, return -1.
 

Definition

    
Class:Rumor
Method:getMinimum
Parameters:String, String[]
Returns:int
Method signature:int getMinimum(String knowledge, String[] graph)
(be sure your method is public)
    
 

Constraints

-knowledge will contain between 1 and 16 characters, inclusive.
-Each character of knowledge will be either 'Y' or 'N'.
-knowledge will contain at least one 'Y' character.
-graph will contain N elements, where N is the length of knowledge.
-Each element of graph will contain N characters.
-Each character of graph will be either 'Y' or 'N'.
-i-th character of i-th element of graph will be 'N'.
 

Examples

0)
    
"YNN"
{"NYN"
,"NNY"
,"NNN"}
Returns: 3
Initially, there are 3 rabbits. Rabbit 0 knows rumor A and B, and other rabbits know nothing.

One of the optimal ways is as follows.
  • On day 1, rabbit 0 sends information about rumor A to rabbit 1.
  • On day 2, rabbit 1 sends information about rumor A to rabbit 2, and rabbit 0 sends information about rumor B to rabbit 1.
  • On day 3, rabbit 1 sends information about rumor B to rabbit 2.
As a result, it takes 3 days.
1)
    
"YNNY"
{"NYYN"
,"YNNY"
,"YNNY"
,"NYYN"}
Returns: 1
One of the optimal ways is as follows.
  • On day 1, rabbit 0 sends information about rumor A to rabbit 1 and rabbit 2, and rabbit 3 sends information about rumor B to rabbit 1 and rabbit 2.
2)
    
"YYYY"
{"NYNN"
,"YNYN"
,"NYNY"
,"NNYN"}
Returns: 0
All rabbits already know the rumors, so no day is required.
3)
    
"YYYYYN"
{"NYYYYN"
,"YNYYYN"
,"YYNYYN"
,"YYYNYN"
,"YYYYNN"
,"NNNNNN"}
Returns: -1
It is impossible to make rabbit 5 know the rumors.
4)
    
"NNNY"
{"NNNN"
,"YNNN"
,"YNNN"
,"NYYN"}
Returns: 3
5)
    
 "NNNNNNNYYY"
{"NYNNYNNYNN"
,"NNYNYNNNNY"
,"YYNNNYNNNN"
,"YNNNYNYNNN"
,"NNYNNYNNYN"
,"NNNNYNNNYY"
,"NYNYNYNNNN"
,"NNNNNNYNYY"
,"NNNYNNNYNY"
,"NYYNNNNYNN"}
Returns: 2

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 525 Round 1 - Division I, Level Two