8

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

DoctorMoisha
  • 1,613
  • 14
  • 25
  • Perhaps the knapsack algorithm would be inspirational? http://en.wikipedia.org/wiki/Knapsack_problem – csl Apr 17 '15 at 10:27
  • 3
    You can start by observing that if `2 * A <= B`, all you'll need is 1x1 tiles. In every other case you'll want to maximise the number of 2x1 tiles. So the real question is: what is the maximum of 2x1 tiles you can fit in the broken spaces? – biziclop Apr 17 '15 at 10:27
  • 1
    And here's a hint that may help: http://en.wikipedia.org/wiki/Mutilated_chessboard_problem – biziclop Apr 17 '15 at 10:33
  • But I suspect (given that the proof of Gomory's theorem apparently uses Hamiltonian cycles) that finding the exact solution will be hard. – biziclop Apr 17 '15 at 10:34
  • 1
    Well the most naive solution is to brute-force it. Just try every possible combination of tiles and calculate the price for each. Computationaly intensive, but will work. – Fox Apr 17 '15 at 10:36
  • Thank you! I have testing system, where time and memory of algorithm is limited, so bruteforce is not an option=) But I'll read all your refernces. – DoctorMoisha Apr 17 '15 at 10:38
  • I am assuming that the price of a 2x1 plate is cheaper than buying 2 1x1 plates? I am also assuming that the bathroom will look the same afterwards, ie. that there's no esthetic requirement here (like a 2x1 plate looks different from 2 1x1 plates). – Lasse V. Karlsen Apr 17 '15 at 11:38

2 Answers2

4

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).

harold
  • 61,398
  • 6
  • 86
  • 164
3

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.

Community
  • 1
  • 1
Rafał Dowgird
  • 43,216
  • 11
  • 77
  • 90