문제1572--Separate Connections

1572: Separate Connections

실행시간 제한: 5 Sec  메모리사용 제한: 128 MB
제출: 274  통과: 60
[제출] [채점기록] [묻고답하기]

문제 설명

You are analyzing a communications network with at most 18 nodes. Assuming a node cannot communicate with two nodes at once, compute the maximum number of nodes that can communicate simultaneously.

입력 설명

Input consists of several test cases.

The first line of each test cases contains a positive integer N, the number of nodes in the communication network. The following N lines contain exactly N character per line and describe a matrix mat. j-th Character in i-th row of mat denotes whether nodes i and j can communicate ('Y' for yes, 'N' for no). You may assume that if node s is communicating with node t then node t is communicating with node s. i-th character of i-th row will be always 'N'.

Note that 1 ≤ N ≤ 18 for all test cases. Input is terminated by EOF.

출력 설명

For each test case, write a single line which gives the maximum number of nodes that can communicate simultaneously.

입력 예시 Copy

5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN

출력 예시 Copy

4

출처/분류