Thông điệp cổ
Đề bài
Mô tả
Để tìm hiểu các nền văn minh cổ đại, các nhà khảo cổ thường nghiên cứu những văn bản viết bằng ngôn ngữ cổ. Một ngôn ngữ như vậy, được dùng ở Ai Cập hơn năm trước, dựa trên các ký tự gọi là chữ tượng hình. Hình C.1 cho thấy sáu chữ tượng hình cùng tên của chúng. Trong bài này, bạn cần viết chương trình nhận dạng sáu ký tự này.

Hình C.1: Sáu chữ tượng hình (từ trái sang phải: Ankh, Wedjat, Djed, Scarab, Was, Akhet).
Dữ liệu vào
Dữ liệu gồm nhiều bộ test, mỗi bộ mô tả một bức ảnh chứa một hoặc nhiều chữ tượng hình chọn trong số các chữ ở Hình C.1. Bức ảnh được cho dưới dạng một dãy các dòng quét ngang gồm các điểm ảnh đen (ký hiệu ) và trắng (ký hiệu ). Trong dữ liệu vào, mỗi dòng quét được mã hóa theo hệ thập lục phân. Ví dụ, dãy tám điểm ảnh 10011100 (một điểm đen, tiếp theo là hai điểm trắng, ...) được biểu diễn trong hệ thập lục phân là 9c. Mã thập lục phân chỉ dùng các chữ số và các chữ cái thường từ a đến f.
Dòng đầu tiên của mỗi bộ test chứa hai số nguyên và : là số dòng quét của bức ảnh, là số ký tự thập lục phân trên mỗi dòng (mỗi ký tự ứng với điểm ảnh, ký tự đầu tiên ứng với điểm ảnh bên trái nhất, bit cao nhất ứng với điểm ảnh bên trái). dòng tiếp theo chứa các ký tự thập lục phân của bức ảnh, theo thứ tự từ trên xuống dưới.
Các bức ảnh tuân theo những quy tắc sau:
- Bức ảnh chỉ chứa các chữ tượng hình có trong Hình C.1.
- Mỗi bức ảnh chứa ít nhất một chữ tượng hình hợp lệ.
- Mỗi điểm ảnh đen đều thuộc một chữ tượng hình hợp lệ.
- Mỗi chữ tượng hình là một tập liên thông các điểm ảnh đen, và mỗi điểm ảnh đen có ít nhất một điểm ảnh đen khác ở ngay phía trên, phía dưới, bên trái hoặc bên phải nó.
- Các chữ tượng hình không chạm nhau và không chữ nào nằm bên trong chữ khác.
- Hai điểm ảnh đen chạm nhau theo đường chéo luôn có một điểm ảnh đen chung kề cạnh với cả hai.
- Các chữ tượng hình có thể bị biến dạng, nhưng mỗi chữ có hình dạng tương đương tô pô với một trong các ký hiệu ở Hình C.1 (hai hình tương đương tô pô nếu có thể biến hình này thành hình kia bằng cách co giãn mà không xé rách).
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test, theo sau là một xâu gồm một ký tự cho mỗi chữ tượng hình nhận dạng được trong ảnh, theo mã sau:
| Chữ tượng hình | Ankh | Wedjat | Djed | Scarab | Was | Akhet |
|---|---|---|---|---|---|---|
| Mã | A |
J |
D |
S |
W |
K |
Trong mỗi xâu kết quả, các mã được in theo thứ tự bảng chữ cái. In theo đúng định dạng Case i: <xâu> như trong ví dụ.
Ràng buộc
- .
- (mỗi dòng có tối đa điểm ảnh).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 6 800000 be3ff8 aa2aa8 ae3ff8 b80000 0 0 |
Case 1: DKW | Bức ảnh điểm ảnh (hình vẽ ví dụ 1 bên dưới): một nét dọc ở cột đầu tiên không bao vùng trắng nào (Was), một hình bao vùng trắng (Akhet) và một hình bao vùng trắng (Djed). |
| 9 4 f900 a900 f97f a955 f97f 0100 e100 a100 e100 0 0 |
Case 1: AJSW | Bức ảnh điểm ảnh (hình vẽ ví dụ 2 bên dưới): một nét dọc chạy suốt từ mép trên xuống mép dưới (Was), một hình bao vùng trắng (Scarab), một hình bao vùng trắng (Wedjat) và một vòng nhỏ bao vùng trắng (Ankh). |
Ví dụ 1 (# là điểm ảnh đen):
grid #....................... #.#####...###########... #.#.#.#...#.#.#.#.#.#... #.#.###...###########... #.###...................
Ví dụ 2:
grid #####..#........ #.#.#..#........ #####..#.####### #.#.#..#.#.#.#.# #####..#.####### .......#........ ###....#........ #.#....#........ ###....#........
Ví dụ chính thức của đề gốc gồm hai bức ảnh lớn ( dòng ký tự và dòng ký tự), quá dài để in ở đây; kết quả tương ứng là Case 1: AKW (Hình C.2) và Case 2: AAAAA (Hình C.3).

Hình C.2: AKW

Hình C.3: AAAAA
Bình luận