Bò chơi ghép hình chữ cái với $R$ hàng ($(1 \le R \le 10)$), $C$ cột ($(1 \le C \le 10)$). Cạnh là chữ, thay vì hình bìa lạ.

Mỗi mảnh có số và $4$ chữ hoặc biên phải khớp như ghép hình thường. Chữ giả 0 (chữ số không) là biên. Mảnh có thể có nhiều biên ở góc hoặc ngay đầu cột của hình $4\times1$. Sáu mảnh dưới là một trong nhiều cách ghép, biên đánh dấu bằng đường thay 0.

              +---+  +---+  +---+
              | 1 c  c 3 d  d 5 |
              +-d-+  + a +  +-e-+

              +-d-+  +-a-+  +-e-+
              | 2 b  b 4 b  b 6 |
              +---+  +---+  +---+

Chữ ở cạnh tiếp xúc khớp nhau, biên đúng ở trên, dưới và hai bên.

Mảnh được biểu diễn bằng số và bốn cạnh theo chiều kim đồng hồ, chữ $a,\ldots,z$ hoặc 0. Có thể cần xoay khi đặt.

Tìm ít nhất một cách ghép. Dữ liệu $R$, $C$ lớn dễ hơn do chữ trên cạnh đa dạng hơn.

Dữ liệu vào

• Dòng $1$: số nguyên $R$ và $C$ cách nhau bởi dấu cách.

• Các dòng $2,\ldots,R\times C+1$: năm mục cách nhau bởi dấu cách, số nguyên định danh và bốn nhãn cạnh.

Dữ liệu ra

• Các dòng $1,\ldots,R\times C$: dòng $R\times (i-1)+j$ mô tả mảnh ở hàng $i$ cột $j$ bằng năm mục: số nguyên định danh, rồi cạnh trên, phải, dưới, trái.

Ví dụ

Dữ liệu vào 1

2 3
1 c d 0 0
2 0 d b 0
3 c 0 d a
4 b a b 0
5 d 0 0 e
6 0 0 b e

Dữ liệu ra 1

1 0 c d 0
3 0 d a c
5 0 0 e d
2 d b 0 0
4 a b 0 b
6 e 0 0 b

Ghi chú

Đầu vào mô tả hình nhưng vài mảnh xoay so với đáp án ví dụ.

Như sơ đồ. Các đáp án khác như phản chiếu cũng có thể; chương trình chấm kiểm tra đáp án.

Tác giả bài toán: Rob Kolstad, 2008