Two-Tiling

Công ty trò chơi của bạn vừa đặt mua rất nhiều bảng vuông gồm 64 ô đơn vị trống để làm bàn cờ vua, nhưng sếp đột nhiên tuyên bố cờ vua đã lỗi thời. Để tận dụng số bảng này, bạn thiết kế một câu đố mới dùng các tile.

Một tile là một tập ô đơn vị liên thông cạnh và có thể đặt vừa trong một hình vuông \(3\times3\). Ví dụ, dưới đây là bốn tile hợp lệ (@ là ô thuộc tile, . chỉ là phần đệm):

...  @@@  @@@  .@@
...  @@@  @.@  @.@
.@.  @@@  @..  @@@

Các hình sau không phải tile hợp lệ: hình đầu không liên thông cạnh, hình thứ hai không nằm vừa trong \(3\times3\), và hình thứ ba cũng không liên thông cạnh.

@@.  @.@  .@@.
...  .@.  @@@@
.@@  @.@  .@@.

Khi đặt một tile, các ô của nó phải trùng khít với những ô bảng chưa bị tile khác phủ. Sau mọi phép tịnh tiến, quay theo bội của \(90^\circ\) và/hoặc phản xạ, tile vẫn được coi là cùng một loại; người giải được phép dùng mọi phép biến đổi ấy. Chẳng hạn, ba hình sau chỉ là các biến thể của cùng một tile:

.@.  ..@  @..
...  @@.  @@.
.@@  @@.  .@@
@@.  .@@  @..
.@.  .@.  @@.

Để tạo câu đố, bạn sẽ tô đỏ một hay nhiều ô bảng. Người chơi phải đặt tile sao cho phủ tất cả và chỉ các ô đỏ. Để tiết kiệm chi phí sản xuất, họ chỉ nhận một loại tile, nhưng nhận vừa đủ số bản sao để phủ toàn bộ ô đỏ.

Bạn phải quyết định tô đỏ những ô nào. Tuy nhiên, sếp vẫn đang chọn giữa hai loại tile. Không muốn chờ nữa, bạn quyết định tìm một tập ô sao cho câu đố giải được bất kể cuối cùng dùng loại tile nào.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test gồm bốn dòng. Mỗi trong ba dòng đầu có ba ký tự, một dấu cách, rồi ba ký tự nữa; dòng thứ tư để trống.

Trong toàn bộ test, dấu cách ngăn lưới \(3\times3\) bên trái với lưới \(3\times3\) bên phải; mỗi lưới là khung hiển thị một tile. Ký tự @ chỉ ô thuộc tile, còn . chỉ là phần đệm để hình dạng rõ ràng và không liên quan đến bảng hay câu đố. Hai tile được bảo đảm khác nhau ngay cả khi cho phép mọi phép biến đổi nêu trên.

Dữ liệu ra

Với mỗi test, trước hết in Case #x: y, trong đó x là số thứ tự test và y là POSSIBLE nếu tồn tại lời giải, ngược lại là IMPOSSIBLE.

Nếu có lời giải, in thêm tám dòng, mỗi dòng đúng 17 ký tự, tạo thành hai lưới \(8\times8\) cách nhau bởi một cột dấu cách. Trong mỗi lưới, dùng . cho ô trống, và dùng các ký tự trong tập 64 ký tự sau để định danh từng tile:

!?0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Trong cùng một lưới, mọi lần xuất hiện của một ký tự khác . phải thuộc đúng một tile; hai ký tự khác nhau phải biểu diễn hai tile khác nhau. Mỗi tile ở lưới trái phải tương đương, qua quay/tịnh tiến/phản xạ, với tile trái của input; quy tắc tương tự áp dụng cho lưới phải. Tập vị trí khác . của hai lưới phải giống hệt nhau và khác rỗng. Nếu có nhiều lời giải, có thể in bất kỳ lời giải nào.

Ràng buộc

• Mỗi tile đầu vào là một nhóm ô liên thông cạnh.
• Hai tile đầu vào không cùng loại theo định nghĩa trên.

Phân nhóm

• Chỉ có Test Set 1 (hiển thị): \(T=595\). Mọi test có thể có, tính đến đẳng cấu, đều xuất hiện.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
.@@ .@.
.@. .@.
.@@ @@.

@@@ @@@
@.@ @@@
@@@ @@@

.@. ...
@@. .@@
@.. ...

... ..@
... ..@
@.. ...

Case #1: POSSIBLE
....11.. ....11..
...221.. ...221..
...211.. ...321..
...22... ...32...
.333.... .433....
4343.... 5444....
444..... 555.....
........ ........
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
........ ........
..T..I.. ..T..I..
.TT..II. .tT..Ii.
.T....I. .t....i.
........ ........
.LL..EE. .LL..EE.
..LLEE.. ..llee..
........ ........
Case #4: POSSIBLE
the.CODE AAB.CDDE
Jam.2018 FFB.CGGE
........ ........
World... HHIIJ...
.FiNALS. .KLLJMM.
.cup.... .KNN....
........ ........
TRIUMPH! OOPPQQRR

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Two-Tiling.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.