This page is still under construction.

Parts of this page are still being built. What you see may change.

Mine Layer (Small)

Time limit5sMemory limit512 MB

Summary
Given a small Minesweeper-style clue grid (R is 3 or 5, C is 3 to 5), find the maximum number of mines the middle row can hold over all layouts that match the clues.
Level

Medium6 of 10

Topics
Brute force, Backtracking, Implementation, Array
Solved
No attempts yet

Problem

MineLayer is a Minesweeper style puzzle played on an RR by CC grid. Each square of the grid holds one mine or no mine at all. A MineLayer puzzle is a grid of numbers, and each number is the total number of mines in every square adjacent to that square plus the square itself. A number is therefore between 0 and 9.

The goal is to find a mine layout that matches the given numbers.

Below is a 3 by 4 grid. The original layout is on the left and the puzzle is on the right.

One grid of numbers can match several layouts, so find the largest number of mines the middle row can hold. The number of rows is always odd, so the middle row is row (R+1)/2(R+1)/2 from the top. Every puzzle has at least one solution.

Input

The first line contains the number of test cases NN. NN test cases follow.

The first line of each test case contains two space separated numbers: RR, the number of rows, and CC, the number of columns. RR is always odd. Each of the next RR lines contains the CC numbers of that row, separated by spaces.

Limits

  • 1≤N≤501 \le N \le 50
  • Every puzzle has at least one solution.
  • R=3R = 3 or R=5R = 5
  • 3≤C≤53 \le C \le 5

Output

For each test case, print one line containing "Case #X: Y", where XX is the 1 based test case number and YY is the largest number of mines the middle row holds among all layouts that satisfy the given numbers.

Examples1

  1. Example 1

    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
    Expected output
    Case #1: 1
Case #2: 1