Minesweeper là một trò chơi máy tính trở nên phổ biến vào những năm 1980 và vẫn được đưa vào một số phiên bản của hệ điều hành Microsoft Windows. Bài toán này có ý tưởng tương tự, nhưng nó không yêu cầu bạn phải từng chơi Minesweeper.

Trong bài toán này, bạn đang chơi một trò chơi trên một lưới gồm các ô giống hệt nhau. Nội dung của mỗi ô ban đầu bị ẩn. Có \(M\) quả mìn được giấu trong \(M\) ô khác nhau của lưới. Không có ô nào khác chứa mìn. Bạn có thể nhấp vào bất kỳ ô nào để mở nó. Nếu ô được mở chứa một quả mìn, trò chơi kết thúc và bạn thua. Ngược lại, ô được mở sẽ chứa một chữ số từ 0 đến 8, tương ứng với số lượng ô lân cận có chứa mìn. Hai ô là lân cận nếu chúng chung một đỉnh hoặc một cạnh. Ngoài ra, nếu ô được mở chứa số 0, thì tất cả các ô lân cận của ô đó cũng tự động được mở, một cách đệ quy. Khi tất cả các ô không chứa mìn đã được mở, trò chơi kết thúc và bạn thắng.

Ví dụ, một cấu hình ban đầu của bảng có thể trông như thế này ('*' biểu thị một quả mìn và 'c' là ô được nhấp đầu tiên):

*..*...**.
....*.....
..c..*....
........*.
..........

Không có quả mìn nào liền kề với ô đã nhấp, vì vậy khi nó được mở, nó trở thành số 0 và 8 ô liền kề của nó cũng được mở. Quá trình này tiếp tục, dẫn đến bảng sau:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

Tại thời điểm này, vẫn còn những ô chưa được mở mà không chứa mìn (được ký hiệu bằng các ký tự '.'), vì vậy người chơi phải nhấp lại để tiếp tục trò chơi.

Bạn muốn thắng trò chơi càng nhanh càng tốt. Không có gì nhanh hơn việc thắng chỉ trong một lần nhấp. Cho kích thước của bảng (\(R \times C\)) và số lượng mìn ẩn \(M\), liệu có thể (dù xác suất thấp đến đâu) thắng chỉ trong một lần nhấp không? Bạn có thể chọn nơi mình nhấp. Nếu có thể, hãy in ra bất kỳ cấu hình mìn hợp lệ nào và tọa độ lần nhấp của bạn, tuân theo các quy định trong phần Dữ liệu ra. Ngược lại, in "Impossible".

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) dòng tiếp theo. Mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách: \(R\), \(C\) và \(M\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x:", trong đó x là số thứ tự bộ test (bắt đầu từ 1). Trên \(R\) dòng tiếp theo, hãy xuất cấu hình bảng với \(C\) ký tự mỗi dòng, sử dụng '.' để đại diện cho một ô trống, '*' để đại diện cho một ô có chứa mìn và 'c' để đại diện cho ô được nhấp.

Nếu không có cấu hình khả thi nào, thay vì lưới, hãy xuất một dòng với "Impossible". Nếu có nhiều cấu hình khả thi, hãy xuất bất kỳ cấu hình nào trong số đó.

Ràng buộc

• \(0 \le M < R \times C\).

Phân nhóm

• Small dataset: \(1 \le T \le 230\); \(1 \le R, C \le 5\).
• Large dataset: \(1 \le T \le 140\); \(1 \le R, C \le 50\).

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

5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82

Case #1:
Impossible
Case #2:
c
.
*
Case #3:
Impossible
Case #4:
......*
.c....*
.......
..*....
Case #5:
**********
**********
**********
****....**
***.....**
***.c...**
***....***
**********
**********
**********

Nguồn

Google Code Jam 2014, Vòng loại, bài Minesweeper Master.

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