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
Một đất nước có N thành phố được đánh số từ 0 đến N – 1. Mỗi cặp thành phố được nối bằng một con đường hai chiều.
John muốn thực hiện một chuyến hành trình như sau:
John xuất phát từ một thành phố bất kì và di chuyển qua mỗi thành phố khác đúng một lần (tất cả là N – 1 chặng).
Ngoài ra, có một số ràng buộc, được cho bởi ma trận A, mỗi phần tử là ký tự 'Y' hoặc 'N'.
- Nếu A(i, j) là ‘Y’, John buộc phải di chuyển qua con đường nối thành phố i với thành phố j.
- Dữ liệu đảm bảo A(i, j) = A(j, i) và A(i, i) = ‘N’.
Đếm số cách John có thể thực hiện được hành trình.
Input
- Dòng đầu tiên chứa số nguyên dương N (2 ≤ N ≤ 50).
- Gồm N dòng, mỗi dòng chứa một xâu gồm N kí tự, mỗi ký tự là 'Y' hoặc là 'N'
Output
- In ra số cách di chuyển có thể trong mô đun 1000000007
Ví dụ 1:
Input Output
Giải thích:
- Có 4 đường có thể đi được mà phải di chuyển qua con đường nối thành phố thành phố 0 và thành phố 1 là:
0->1->21->0->22->0->12->1->0.
- Riêng 0->2->1 và 1->2->0 không được tính vì không có đi qua con đường nối 0 và 1
Ví dụ 2:
Input Output
Ví dụ 3:
Input Output
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...