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 M×N 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 M×N grid. Specify the maximum number of knights (black and 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 separated by a single space
This is followed by a grid of size M×N 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 <= Number of open positions "." <= 10
Example
Input: 2 3 3 ... ... ... 3 3 ... .#. ... Output: 7 6
hide comments
dce coders:
2012-04-26 13:35:44
Updated. M rows, N columns. |
|
:D:
2012-04-25 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: | 2012-04-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own Problem |