Hình vuông Latin
Đề bài
Mô tả
Hình vuông Latin là một bảng được điền số nguyên từ đến sao cho mỗi số xuất hiện đúng một lần trên mỗi hàng và trên mỗi cột.
Ví dụ, sau đây là một hình vuông Latin:
| 1 | 2 | 3 |
| 2 | 3 | 1 |
| 3 | 1 | 2 |
Gon rất thích hình vuông Latin và đang tạo một hình vuông như vậy.
Đầu tiên Gon tạo một bảng trống gồm hàng và cột. Sau đó Gon viết số vào bảng, dùng số khác nhau, mỗi số xuất hiện đúng lần, sao cho trên mỗi hàng và mỗi cột không có số nào xuất hiện quá một lần.
Tuy nhiên, Gon không biết phải làm tiếp như thế nào. Hãy giúp Gon điền nốt hình vuông Latin. Tất nhiên, bạn không được xóa số nào Gon đã viết, tức là bạn chỉ được viết vào các ô trống.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ).
Mỗi dòng trong dòng tiếp theo chứa số nguyên mô tả bảng. Các số nằm trong đoạn từ đến , trong đó là ô trống.
Dữ liệu đảm bảo trên mỗi hàng và mỗi cột không có hai ô nào cùng giá trị dương, và trong bảng có đúng số dương khác nhau, mỗi số xuất hiện đúng lần.
Dữ liệu ra
Nếu không có lời giải, in ra đúng một dòng NO.
Ngược lại, in ra YES, sau đó là dòng, mỗi dòng chứa số: hình vuông Latin đã điền đầy đủ.
Nếu có nhiều lời giải, in ra một lời giải bất kỳ.
Ràng buộc
- , .
- Bảng có đúng giá trị dương khác nhau, mỗi giá trị xuất hiện lần, không giá trị nào lặp lại trên một hàng hay một cột.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 0 0 0 2 0 0 0 2 |
YES 2 1 3 3 2 1 1 3 2 |
Số đã nằm trên đường chéo chính. Các số và được điền vào các ô trống sao cho mỗi hàng và mỗi cột có đủ . |
| 2 0 0 0 0 0 |
YES 1 2 2 1 |
Ví dụ bổ sung (không có trong đề gốc). Bảng trống, điền một hình vuông Latin bất kỳ. |
Bình luận