0.Làng thống trị
Submit solution
Points:
5
Time limit:
1.5s
Memory limit:
98M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Trong một nước cổ đại, có N làng khác nhau ( được đánh số từ 0-> N-1) , và làng A thống trị làng B khi đường đi từ 1 làng được chỉ định trước ( gọi là làng X ) về làng B bắt buộc phải đi qua làng A, và từ A sẽ tồn tại đường đi đến B. Nếu từ X mà không thể đến làng Y bất kì thì làng Y này sẽ không bị thống trị bởi bất cứ làng nào. Với bài toán này, làng X sẽ có chỉ số là 0.
Ví dụ:
Nhìn vào hình trên, Làng 3 sẽ thống trị làng 4 vì mọi con đường đến 4 bắt buộc phải đi qua 3. Làng 1 không thống trị làng 3 bởi đường đi đến 3 có 0->2->3 không đi qua 1.
Input:
- số test T ( T <= 100 ) Trong mỗi test :
- Dòng đầu bao gồm số N ( N <= 100 ) là số làng
- i trong N dòng tiếp theo ( bắt đầu từ 0 ), mỗi dòng bao gồm N số, số thứ j ( bắt đầu từ 0 ) có giá trị 1 cho biết có đường đi trực tiếp từ làng i đến làng j. ngược lại, giá trị 0 cho biết không có đường đi trực tiếp từ làng i đến làng j Chú ý rằng: Đường đi trên là đường 1 chiều.
Output:
Ứng với mỗi test:
- In ra thông tin số test tương ứng
- Tiếp đến là 2*N + 1 dòng cho biết quan hệ thống trị giữa từng cặp làng.Nếu làng A thống trị làng B thì tại vị trí ( A,B ) in ra "Y".ngược lại in "N". Vị trí (A,B) có nghĩa là hàng thứ A và cột thứ B ( bắt đầu từ 0 ). Bao quanh output là các kí tự : '|' , '+', '-' cho định dạng rõ ràng.nhìn output dưới đây để hiểu rõ.
Sample Input
2
5
0 1 1 0 0
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
1
1Sample Output
Case 1:
+---------+
|Y|Y|Y|Y|Y|
+---------+
|N|Y|N|N|N|
+---------+
|N|N|Y|N|N|
+---------+
|N|N|N|Y|Y|
+---------+
|N|N|N|N|Y|
+---------+
Case 2:
+-+
|Y|
+-+
Comments
k copy đc test :(
done !!