Doors
SRM 835 · 2022-08-15 · by misof
Problem Statement
You are given the
Two rooms are considered adjacent if they share a side.
Building a door between two adjacent rooms in the same row of the plan costs 1. Building a door between two adjacent rooms in the same column of the plan costs 2.
The initial plan of the architect of the building was to have a door between each pair of adjacent rooms. However, the times are rough and so you decided to save some money.
A set of doors is called sufficient if it allows you to move inside the building as well as a full set of doors would. More formally, if it's possible to go from one room to another in a building that has the given floor plan and all possible doors, it must also be possible to go there (possibly using a longer path) in the building that has the same floor plan but only your set of doors built between them.
Find and return the total cost of the cheapest sufficient set of doors for the given building.
Constraints
- plan will contain between 1 and 30 elements, inclusive.
- Each element of plan will contain between 1 and 30 characters, inclusive.
- All elements of plan will contain the same number of characters.
- Each character in plan will be '.' or '#'.
{"..",
".."}
Returns: 4
Four rooms, arranged in a 2 by 2 pattern. The original plan was to buy four doors: one in each row and one in each column. But clearly it is sufficient to buy any three out of those doors, and the cheapest way to do that is to buy both doors in rows and one of the two doors in columns. This costs 1+1+2 = 4. Below is a drawing of the resulting house, with +-| used to draw walls around rooms. The rooms in the drawing are numbered 0, 1, 2, 3. The spaces between numbers represent the actually built doors. +-+-+ |0 1| + +-+ |2 3| +-+-+
{".#.#.#",
"#.#.#.",
".#.#.#"}
Returns: 0
There are no two adjacent rooms in this building, so no doors are getting built.
{".#..",
".###"}
Returns: 3
Two rooms in the same row, and elsewhere in the building two rooms in the same column. Each pair of rooms needs to get a door between them.
{".#.",
"..."}
Returns: 6
Here we need to buy all four possible doors: one in column 0, one in column 2, and two in row 1.
{".....",
"...#.",
".....",
"....."}
Returns: 22
Here we can save a bunch of money. Below is one optimal layout. We build 14 doors in rows and 4 doors in columns for a total cost of 14*1 + 4*2 = 22. +-+-+-+-+-+ + + +-+-+-+-+ + + |#| + + +-+-+-+ + + + + +-+-+-+-+ + + +-+-+-+-+-+
Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Doors with a public method int build(vector<string> plan) · 120 test cases · 2 s / 256 MB per case