1721: Strange Country
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:1
解决:0
题目描述
There is a country with N cities, some of which are connected with
bidirectional roads. Your task is to reconfigure the roads so that it is possible
to get from each city to every other city. You must do this using the minimum
possible number of transformations, where each transformation consists of the
following steps:
Choose four different cities A, B, C and D, where roads (A, B) and (C, D) exist,
but (A, C), (A, D), (B, C) and (B, D) do not exist.
Destroy roads (A, B) and (C, D).
Build two new roads - either (A, C) and (B, D), or (A, D) and (B, C).
The following images show an example of this transformation. From the first
situation you can get the second one or the third one:
You are given a map[i][j], map[i][j] is ‘Y‘ if there is a road between cities i and j, and ‘N‘ otherwise. Return minimal number of transformations required to accomplish your task, or return -1 if it is impossible.
Constraints
- 2<=N<=50
- For each i and j, map[i][j] will be equal to map[j][i].
- For each i, map[i][i] will be equal to ‘N‘.
输入
*Line 1: N
*Line 2...1+N: The jth element of line i describing map[i][j]
输出
*Line 1: A single integer that the minimal number of transformations required
样例输入 复制
2
NY
YN
5
NYYNN
YNYNN
YYNNN
NNNNY
NNNYN
样例输出 复制
0
1
提示
The second sample transformations is like the images followed