JOIN
Get Time

   Problem Statement  

 Problem Statement for SeparateConnections

Problem Statement

    You are analyzing a communications network with at most 18 nodes. Character j in element i (both 0-based) of mat denotes whether nodes i and j can communicate ('Y' for yes, 'N' for no). Assuming a node cannot communicate with two nodes at once, return the maximum number of nodes that can communicate simultaneously.
 

Definition

    
Class:SeparateConnections
Method:howMany
Parameters:String[]
Returns:int
Method signature:int howMany(String[] mat)
(be sure your method is public)
    
 

Notes

-If node S is communicating with node T then node T is communicating with node S.
 

Constraints

-mat will contain between 1 and 18 elements inclusive.
-Each element of mat will contain exactly N characters, where N is the number of elements in mat.
-Each character in mat will be 'Y' or 'N'.
-Character i of element i of mat will be 'N'.
-Character i of element j will be the same as character j of element i.
 

Examples

0)
    
{
"NYYYY",
"YNNNN",
"YNNNN",
"YNNNN",
"YNNNN"
}
Returns: 2
All communications must occur with node 0. Since node 0 can only communicate with 1 node at a time, the returned value is 2.
1)
    
{
"NYYYY",
"YNNNN",
"YNNNY",
"YNNNY",
"YNYYN"
}
Returns: 4
In this setup, we can let node 0 communicate with node 1, and node 3 communicate with node 4.
2)
    
{
"NNYYYYYYYYYYYYYYYY",
"NNYYYYYYYYYYYYYYYY",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN",
"YYNNNNNNNNNNNNNNNN"
}
Returns: 4
3)
    
{
"NNNNNNNNNYNNNNNYN",
"NNNNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNNNN",
"NNNNNYNNNNNYNNYYY",
"NNNNNNNNNNNNNNNYN",
"NNNYNNNNNNNNNNYNN",
"NNNNNNNNNYNNNNNNN",
"NNYNNNNNNNNNNNNNN",
"NNNNNNNNNYNNNNNNN",
"YNNNNNYNYNNNNNNNY",
"NNNNNNNNNNNNNNNNN",
"NNNYNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNN",
"NNNYNYNNNNNNNNNNN",
"YNNYYNNNNNNNNNNNN",
"NNNYNNNNNYNNNNNNN"
}
Returns: 10

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:
       TCO 06 Online Round 1 - Division I, Level One
       TCO 06 Sponsor Track Round 1 - Division I, Level Two