MineLayer là một trò chơi giải đố giống như Dò mìn (Minesweeper) được chơi trên một lưới kích thước \(R \times C\). Mỗi ô vuông trong lưới có thể có một quả mìn hoặc không có quả mìn nào. Một câu đố MineLayer bao gồm một lưới các con số, mỗi con số cho biết tổng số mìn trong tất cả các ô liền kề và trong chính ô mang con số đó (tức là tối đa 9 ô của hình vuông \(3 \times 3\) có tâm tại ô ấy). Do đó, các con số sẽ nằm trong khoảng từ 0 đến 9.

Mục tiêu của MineLayer là tìm ra một cách bố trí các quả mìn trong lưới khớp với các manh mối đã cho.

Dưới đây là một lưới \(3 \times 4\) điển hình. Cách bố trí ban đầu ở bên trái và câu đố ở bên phải.

Vì có thể có nhiều lời giải, nhiệm vụ của bạn là viết một chương trình xuất ra số lượng mìn tối đa có thể có ở hàng giữa. Số hàng \(R\) sẽ luôn là một số lẻ và luôn đảm bảo có ít nhất một lời giải cho câu đố.

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, \(N\). Tiếp theo là \(N\) bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số cách nhau bởi dấu cách: \(R\), số hàng và \(C\), số cột. \(R\) luôn là một số nguyên lẻ. Mỗi dòng trong số \(R\) dòng tiếp theo chứa \(C\) số cách nhau bởi dấu cách biểu thị các manh mối của hàng đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng chứa "Case #X: Y", trong đó X là số thứ tự bộ test (bắt đầu từ 1) và Y là số lượng mìn tối đa có thể có ở hàng giữa của lưới thỏa mãn các ràng buộc đã cho.

Ràng buộc

• \(1 \le N \le 50\).
• Mỗi câu đố được đảm bảo có ít nhất một lời giải.

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible):
• \(R = 3\) hoặc \(R = 5\).
• \(3 \le C \le 5\).
• Tập dữ liệu lớn (Test set 2 - Hidden):
• \(R\) là một số lẻ nằm trong khoảng từ 3 đến 49, bao gồm cả hai đầu.
• \(3 \le C \le 49\).

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

2
3 3
2 2 1
3 4 3
2 3 2
3 4
1 2 1 1
2 3 3 2
2 2 2 1

Case #1: 1
Case #2: 1

Nguồn

Google Code Jam 2008, Chung kết thế giới, bài Mine Layer.

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