Hình vuông đẹp
Đề bài
Mô tả
Harry thích vẽ, và Harry cũng thích hình vuông. Hôm nay Harry sẽ vẽ một hình vuông.
Hình vuông của Harry được chia thành ô vuông đơn vị. Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải.
Trong mỗi ô, Harry sẽ viết một số nguyên trong đoạn . Theo Harry, một hình vuông là đẹp khi và chỉ khi thỏa mãn cả hai điều kiện sau:
- Mỗi số nguyên từ đến được viết trong đúng một ô.
- Với mỗi từ đến , hai số và được viết trong hai ô có chung một cạnh.
Harry đã vẽ một hình vuông kích thước và đã viết số vào một ô nào đó. Hãy giúp Harry viết các số từ đến để tạo thành một hình vuông đẹp.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm một dòng chứa ba số nguyên , , : kích thước hình vuông, hàng và cột của ô chứa số .
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Nếu không thể tạo được hình vuông đẹp, in ra một dòng chứa NO.
- Ngược lại, in ra YES, tiếp theo là dòng, mỗi dòng chứa đúng số nguyên mô tả hình vuông đẹp. Nếu có nhiều cách, in ra cách bất kỳ.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 1 1 5 1 2 |
YES 1 2 3 4 16 7 6 5 15 8 9 10 14 13 12 11 NO |
Với bộ thứ nhất, các số tăng dần theo một đường đi qua mọi ô, mỗi bước sang một ô kề cạnh. Một đáp án khác cũng được chấp nhận là đi theo hình rắn từng hàng: 1 2 3 4 / 8 7 6 5 / 9 10 11 12 / 16 15 14 13. Với bộ thứ hai, không tồn tại hình vuông đẹp. |
| 3 1 1 1 3 2 2 2 1 2 |
YES 1 YES 3 4 5 2 1 6 9 8 7 YES 4 1 3 2 |
Hình vuông chỉ có số . Với , số ở ô chính giữa; đường đi qua cả ô. |
Bình luận