Đề bài

Hai công ty, Apricot Rules LLC và Banana Rocks Inc., đang dùng chung một trung tâm dữ liệu. Trung tâm dữ liệu là một ma trận gồm \(R\) hàng và \(C\) cột, mỗi ô chứa một tháp máy chủ. Mỗi tháp chứa tài sản trí tuệ thuộc về đúng một trong hai công ty.

Ban đầu, họ xây tường trên các cạnh ngăn cách những ô được giao cho hai công ty khác nhau. Nhờ đó, các ô kề nhau theo cạnh và thuộc cùng một công ty vẫn được nối với nhau. Ngoài ra, hai ô \(x\) và \(y\) được coi là liên thông nếu \(x\) được nối với một ô mà ô đó liên thông trực tiếp hoặc gián tiếp với \(y\). Theo định nghĩa này, vẫn có thể tồn tại hai ô được giao cho cùng một công ty nhưng không liên thông với nhau, và điều đó là không thể chấp nhận.

Hai công ty đồng ý xây các hành lang hẹp đi qua góc ô để nối trực tiếp hai ô kề nhau theo đường chéo. Ký hiệu \((i, j)\) là ô ở hàng \(i\), cột \(j\). Qua mỗi đỉnh chỉ được xây nhiều nhất một hành lang hẹp; nghĩa là có thể nối \((i, j)\) với \((i + 1, j + 1)\), hoặc nối \((i + 1, j)\) với \((i, j + 1)\), hoặc không nối cặp nào, nhưng không được nối cả hai cặp. Dĩ nhiên, chỉ được xây hành lang giữa hai ô được giao cho cùng một công ty.

Cho một ma trận mà mỗi ô được gắn nhãn A hoặc B tùy theo công ty sở hữu ô đó. Hãy tìm cách thêm các kết nối giữa những ô kề nhau theo đường chéo sao cho tất cả các ô A liên thông với nhau và tất cả các ô B liên thông với nhau.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\), lần lượt là số hàng và số cột của ma trận biểu diễn trung tâm dữ liệu. Sau đó là \(R\) dòng, mỗi dòng chứa \(C\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) trong số các dòng này, \(M_{i,j}\), là A hoặc B, cho biết công ty sở hữu ô \((i, j)\).

Dữ liệu ra

Với mỗi bộ test, trước tiên hãy in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)), còn y là IMPOSSIBLE nếu không có cách chọn các kết nối theo đường chéo sao cho các ô A liên thông và các ô B liên thông, hoặc là POSSIBLE nếu tồn tại cách chọn. Sau đó, nếu đã in POSSIBLE, hãy in thêm \(R - 1\) dòng, mỗi dòng gồm \(C - 1\) ký tự. Các ký tự này phải biểu diễn một cách bố trí hợp lệ như mô tả ở trên. Ký tự thứ \(j\) trên dòng thứ \(i\) trong số các dòng đó phải là \ nếu cần nối hai ô \((i, j)\) và \((i + 1, j + 1)\), là / nếu cần nối hai ô \((i + 1, j)\) và \((i, j + 1)\), hoặc là . nếu không nối cặp nào.

Ràng buộc

• \(1 \le T \le 100\).
• \(2 \le C \le 100\).
• \(M_{i,j}\) là chữ cái viết hoa A hoặc chữ cái viết hoa B với mọi \(i\) và \(j\).
• \(M_{i,j}\) là chữ cái viết hoa A với ít nhất một cặp \(i, j\).
• \(M_{i,j}\) là chữ cái viết hoa B với ít nhất một cặp \(i, j\).

Phân nhóm

Test Set 1 (Hiển thị)

• \(2 \le R \le 4\).

Test Set 2 (Ẩn)

• \(2 \le R \le 100\).

Đ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ụ

3
2 2
AB
BA
2 3
AAB
ABB
3 4
BBAA
BABA
BBAA

Case #1: IMPOSSIBLE
Case #2: POSSIBLE
..
Case #3: POSSIBLE
//\
.//

Nguồn

Google Code Jam 2019, Vòng 3, bài Datacenter Duplex.

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