Fixing floor algorithm

Question

Okay, I have this task: John's bathroom floor was broken. We have a map of this floor, where '.' is good plate, and '+' is bad plate, for example:

.+++
.+.+

Here we have 5 broken plates, and 3 good ones. There are two kinds of plates, which are sold in shop: 1x1 plates and 2x1 plates. 1x1 plate costs A, and 2x1 plate costs B. Task is: given map of floor, count minimum price of floor fixing.

Looking at example on top: we can place 2 2x1 plates and 1 1x1 plate. So price will be A+2*B.

I have an idea: for every broken plate count maximum length of connected broken plates. Then price is length/2*B + length%2*A.

Problem is, that I really don't know how to do it. I have an idea of some recursive algorithm, but there are so many problems like circles:

+++
+.+
+++

So I have two questions:

1. Am i going in the right direction?
2. Can you give me any hints on implementing this algorithm?

Thank you!

EDIT

There is trivial case when 2*A < B, but let's talk about non-trivial=)

/EDIT

Answer 1

Classic tiling problem. It's a weighted exact cover, in the non-trivial case (when using two 1x1 tiles costs more than using one 1x2 tile) I'd use ZDDs to solve it. Look in The Art of Computer Programming V4 1B for an example (dominos on a chessboard).

There are libraries available (for example CUDD) so you don't have to implement ZDDs from scratch, though that isn't too hard either.

As a bonus, you can get also get other information that's usually not supplied by other algorithms, such as the number of valid tilings without enumerating them all. It also easily generalizes to other sizes/shapes of tile (3x1, 2x2, L-piece, etc).

Answer 2

If 2*A<=B then this is trivial, just cover everything with 1x1s.

In the opposite case you have to maximize the number of 2x1s. The fact that the tiles are exactly 2x1 makes it easier than the general tiling problem. In particular this is equivalent to finding a maximum cardinality matching in a bipartite graph, see my answer here.

Once you find the maximum configuration of 2x1, you just have to cover the rest of the tiles with 1x1s.