0 人解决，3 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。
2497. Mine Layer
单点时限: 2.0 sec
内存限制: 256 MB
MineLayer is a MineSweeper-like puzzle game played on an R by C grid. Each square in the grid either has one mine or no mines at all. A MineLayer puzzle consists of a grid of numbers, each of which indicates the total number of mines in all adjacent squares and in the square underneath. The numbers will thus range from zero to nine.
The objective of MineLayer is to figure out a layout of the mines in the grid that matches the given clues.
Below is a typical 3 by 4 grid. The original layout is on the left, and the puzzle on the right.
Since there may be many solutions, your task is to write a program that outputs the maximum possible number of mines in the middle row. The number of rows will always be odd, and there will always be at least one solution to the puzzle.
输入格式
The first line of input gives the number of cases, N(1 ≤ N ≤ 50). N test cases follow.
The first line of each case contains two space-separated numbers: R, the number of rows, and C(3 ≤ C ≤ 49.), the number of columns. R is always an odd integer. Each of the next R lines contains C space-separated numbers that denote the clues of that row.
Each puzzle is guaranteed to have at least one solution.
R is an odd number between 3 and 49, inclusive.
输出格式
For each test case, output one line containing “Case #X: Y”, where X is the 1-based case number, and Y is the maximum possible number of mines in the middle row of a grid that satisfies the given constraints.
样例
Input
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
Output
Case #1: 1 Case #2: 1
题目标签