Time Limit: 2 second(s) | Memory Limit: 32 MB |
There is an M x N board, two types of tiles are available, and each of them is infinitely many, you have to place maximum number of non-overlapping tiles in the board. The tiles are given below:
You cannot rotate or flip any tile. Some cells in the board may be broken; you can't place any part of a tile in the broken cells.
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing two integers: M N (2 ≤ M ≤ 8, 2 ≤ N ≤ 100). Each of the next M lines contains N characters forming the board. There are two types of characters. A '.' means the cell is not broken; a '#' means the cell is broken.
For each case, print the case number and maximum number of tiles that can be placed in the board.
Sample Input |
Output for Sample Input |
3 2 3 ... ... 2 3 ..# ... 5 6 .#.... ...... ...... ....#. ..#... |
Case 1: 1 Case 2: 0 Case 3: 3 |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |