DCEPC502  Just Like the Good Old Days
Sheldon and Penny are neighbours. Penny really likes grid games so Sheldon develops a new grid based game for Penny. The game consists of a MXN grid (M rows, N columns) and an infinite number of black and white knights. The grid has some open and some closed blocks. In the beginning of the game each player chooses his colour of knight.The rule says that each player on his turn can place his knight on any of the open blocks such that none of his knights attack any knight of other colour (he may attack any knight of the same colour). You are given a MXN grid. Specify the maximum number of knights (black+white) which can be placed on the grid. The game stops when any one player cannot place any more knights.
Note: In one turn, Knight can move exactly two squares horizontally and one square vertically, or two squares vertically and one square horizontally.
Input
First line specifies T, the number of test cases.
First line of each test case gives M and N seperated by a single space
This is followed by a grid of size MXN consisting of ‘.’ And ‘#’. Each ‘.’ represents an open
position and each ‘#’ represents closed position.
Output
Output 1 line for each test case giving the maximum possible value of knights that can be placed.
Constraints
1<=T<=5
1<=M,N<=10
0<= No. of open positions "." <=10
Example
Input: 2 3 3 ... ... ... 3 3 ... .#. ... Output: 7 6
hide comments
Simes:
20130726 13:57:29
Is there a reason Pascal isn't allowed? 

dce coders:
20120426 13:35:44
Updated. M rows, N columns. 

:D:
20120425 12:52:54
Could you specify witch of M and N stand for rows and columns count? My program was written to work both ways, but it would be nice to clarify. 
Added by:  dce coders 
Date:  20120418 
Time limit:  0.566s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 