Nội dung Bài tập
- Mã:
-
MINIGAME41.3:
HANHTRINH
- Tên:
- Thực hiện hành trình
- Dạng thi:
- oi
- Thang điểm:
- 40 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phuc
There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.
John plans to travel through the country using the following rules:
- He must start in one city and end in another city after travelling exactly N-1 roads.
- He must visit each city exactly once.
- You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.
Return the number of paths he can choose, modulo 1,000,000,007.
Constraints
- Roads will contain between 2 and 50 elements, inclusive.
- Each element of roads will contain n characters, where n is the number of elements in roads.
- Each character in roads will be 'Y' or 'N'.
- The i-th character in the i-th element of roads will be 'N'.
- The j-th character in the i-th element of roads and the i-th character in the j-th element of roads will be equal.
Examples
Input Output 3 NYN YNN NNN4
The example from the problem statement
Input Output 4 NYYY YNNN YNNN YNNN0
It's impossible to travel all these roads while obeying the other rules.
Input Output 3 NYY YNY YYN
This is also impossible.
Input Output 6 NNNNNY NNNNYN NNNNYN NNNNNN NYYNNN YNNNNN24
Theme :
|
Ai có thể xem bài này :
Phần thảo luận
LTNC_Thứ 3