SRM 383, D1, 500-Pointer (FloorBoards)

James S. Plank


If you are a COSC594 student and I have assigned you this problem, please make sure you understand and present the solution below. If you google it and find the solution online, that's fine, but don't try to present that solution. As it turns out, it works using the same principle as I describe below, but it is much harder to understand. I suspect that the students who have tried to present it in the past didn't solve it themselves, but instead took the online solution and then tried to present how it worked. It didn't go well, so please work through my notes below and write the code yourself.
I gave this as a lab in CS302 in 2011. Ha ha. This is from the lab writeup.

The strategy here is not obvious, so I'll help you out. Since room.size() and room[i].size() are capped at 10, you should be thinking "enumeration." You should also think "sentinel". The first thing that I did was sentinelize room so that the first line was all #'s, and the remaining lines end with a '#'. Now, you could try to enumerate all possible flooring configurations. That would be 2n where n is equal to the total number of "."'s in room. Which means it could be as bad as 2100. That won't do. However, you can instead work row-by-row, and at each step you enumerate all possible flooring combinations for just that row. That's only 210 combinations per row, which is very doable. Here's how it works:

At each step, I work on room[r] for r going from 1 to room.size()-1. For that step, I maintain four vectors:

Obviously, at the end of each step, you'll simply copy current_boards to last_boards and current_nplanks to last_nplanks. Since you've sentinelized room so so that room[0] has all #'s, on the first pass, last_board contains one element: room[0], and last_nplanks contains only the integer 0, because ther are no ways to floor that row.

Now, at each pass, you should create current_boards by enumeration. A simple recursive procedure will do it. After creating current_boards, you create current_nplanks. For each board current_boards[i], you run through every last_boards[j] and calculate how many boards will be required to floor when the last two rows are current_boards[i] and last_boards[j]. Take the minimum value of these and that will be current_nplanks[i].

When you're done, the minimum value in current_nplanks will be the value of the optimum flooring.


Let's go through an example, when room = { "##.", "...", "##." }. There is one minimum flooring, which requires two boards:

##|
--|
##|

In the table below, I include the value of the four vectors at each pass of the algorithm. I've sentinelized room.

< <
r room[r-1] room[r] last_boards last_nplanks current_boards current_nplanks
1 "####" "##.#" { "####" } { 0 } { "##|#" "##-#" } { 1, 1 }
2 "##.#" "...#" { "##|#" "##-#" } { 1, 1 }{ "|||#" "||-#" "|-|#" "|--#"
"-||#" "-|-#" "--|#" "---#" }
{ 3, 4, 3, 3,
3, 4, 2, 2 }
3 "...#" "##.#" { "|||#" "||-#" "|-|#" "|--#"
"-||#" "-|-#" "--|#" "---#" }
{ 3, 4, 3, 3,
3, 4, 2, 2 }
{ "##|#" "##-#" } { 2, 3 }

To help, focus on when r equals 2 and current_board[i] is equal to "|||". You check both elements of last_boards. The first, last_boards[0], equals "##|#" and can be floored with one board. If you floor the next row of room with "|||#", then it will require two more boards, since the one in the last column will be attached to the board in the row above. That's a total of 3 boards. When you look at last_boards[1], it equals "##-#", and if you floor the next row of room with "|||#", it will require three extra boards, for a total of four. Thus, the entry of current_nplanks that corresponds to "|||#" will have a value of 3 (the minimum of 3 and 4).