National Treasures#1280
To help secure the hall, the museum has contracted a private security company to provide additional guards to monitor the ancient artifacts. The museum wishes to hire the minimum number of additional guards so that the great hall is secure.
The great hall is represented as a two-dimensional grid of R \times C cells. Some cells are already occupied by the museum's guards. All other cells are occupied by artifacts of different types (statues, sculptures, etc.), which may be replaced by newly hired guards. For each artifact, a few other cells in the hall are identified as critical points depending on the artifact's value, the type of vault it is stored in, and other factors. In other words, if an artifact remains in the hall, then a guard must be standing at each of its critical points. A guard standing at a critical point for multiple artifacts can monitor them all. However, a guard cannot stand in a cell that contains an artifact (instead, you may remove the artifact to place a guard in that cell). You also cannot remove an artifact and leave the cell empty; you can only replace an artifact with a newly hired guard.
Upon surveying all the artifacts in the great hall, you have determined that the critical points of any artifact (marked by a *) are always a subset of the neighboring cells as shown in the grid below.
Accordingly, the type of an artifact can be specified as a non-negative integer, where the -th bit is if and only if critical point number (in the picture above) is a critical point of that artifact. For example, an artifact of type (in binary ) can be represented as shown in the figure below. Note that bits are numbered from right to left (the rightmost bit is bit number ). If a critical point of an artifact lies outside the hall grid, it is considered secure.
You are given the layout of the great hall and are asked to find the minimum number of additional guards to hire so that all remaining artifacts are secured.
Your program will be tested on one or more test cases. Each test case is defined using R+1 lines. The first line contains two integers (1 \le R, C \le 50), the dimensions of the museum hall. The next lines each contain integers separated by spaces. The -th integer of the -th row is if cell already contains one of the museum's guards. Otherwise, it contains an integer (0 \le T < 2^{12}) representing the type of artifact in that cell.
The last line of the input file contains two zeros.
For each test case, print the following line:
where is the test case number (starting at one) and is the minimum number of additional guards to hire so that all remaining artifacts are secured.
The picture on the right shows the solution for the second test case, where the two artifacts in the middle are replaced by guards.
Example 1