Prevent Cheating

All submissions for this problem are available.
Due to the decreasing quality of students in each new session , all the teachers formed a committee and came up with a decision of changing the seating pattern of students in class.
The classroom can be regarded as a rectangle of M rows by N columns of unit squares, where each unit square represents a seat. The teachers decided to set the following rule to prevent cheating. Assume a student is able to see his left, right, upperleft, and upperright neighbors' answer sheets. The assignment of seats must guarantee that nobody's answer sheet can be seen by any other student.
Some seats of the classroom are broken and no student can be made to sit on the broken seat.
Your goal is to find the maximum number of students that can be placed in the classroom so that no one can cheat.
Input
The first line of input gives the number of cases, C. C test cases follow. Each case consists of two parts.
The first part is a single line with two integers M and N: The height and width of the rectangular classroom.
The second part will be exactly M lines, with exactly N characters in each of these lines. Each character is either a '.' (the seat is not broken) or 'x' (the seat is broken, lowercase x).
Output
For each test case, output one line containing "Case #X: Y", where X is the case number, starting from 1, and Y is the maximum possible number of students that can take the exam in the classroom.
Constraints
C = 20 1 ≤ M ≤ 80 1 ≤ N ≤ 80
Example
Input: 4 2 3 ... ... 2 3 x.x xxx 2 3 x.x x.x 10 10 ....x..... .......... .......... ..x....... .......... x...x.x... .........x ...x...... ........x. .x...x.... Output: 4 1 2 46
Author:  shivendra14 
Tags  shivendra14 
Date Added:  27022013 
Time Limit:  0.1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 