trang chủ / đề bài / icpcwf11_c

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 3000 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 1) và trắng (ký hiệu 0). 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 H và W: H là số dòng quét của bức ảnh, W là số ký tự thập lục phân trên mỗi dòng (mỗi ký tự ứng với 4 điểm ảnh, ký tự đầu tiên ứng với 4 điểm ảnh bên trái nhất, bit cao nhất ứng với điểm ảnh bên trái). H 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ố 0.

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

  • 0<H≤200.
  • 0<W≤50 (mỗi dòng có tối đa 200 đ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 5×24 đ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 2 vùng trắng (Akhet) và một hình bao 5 vùng trắng (Djed).
9 4
f900
a900
f97f
a955
f97f
0100
e100
a100
e100
0 0
Case 1: AJSW Bức ảnh 9×16 đ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 4 vùng trắng (Scarab), một hình bao 3 vùng trắng (Wedjat) và một vòng nhỏ bao 1 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 (100 dòng × 25 ký tự và 150 dòng × 38 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0