KingdomXEmergencyStaircase
A city has imposed new safety measures for its buildings. An emergency staircase is going to be built between the only two tall buildings in Linear Kingdom. These buildings are side-by-side and are infinitely tall. The lowest floor is floor 0 on the ground. The distance between two adjacent floors is two meters. The sides of the buildings are parallel and the distance between the buildings is Width meters, where Width is an even integer. The illustration below shows the bottom of the buildings when the buildings are separated by 4 meters (note that for simplicity only the first six floors are labeled):
Normally a staircase is a structure composed of "flights" (or "flights of stairs") and "landings." A flight is a continious sequence of stairs (steps), usually the same size and in the same direction, which begins and ends on flat areas called landings. For this problem we will use an idealized staircase where landings are a single points and flights are straight line segments.
Each flight that is going to be built is a straight line segment whose slope is either 1 or -1. The picture below illustrates two examples of flights.
Some floors of the buildings have emergency exits. These exits are going to be connected to the ground through the staircase. You are given Strings leftBuilding and rightBuilding. The i-th character (1-based indexing) of leftBuilding (rightBuilding) will be 'Y' if there is an emergency exit on floor i of the left building (right building). Note that this implies that no emergency exit will be on floor 0.
Initially, all floors except floor 0 are not connected to the ground. The procedure for building the staircase will be as follows:
- You pick a point that is connected to the ground (this point must be located on the staircase or on floor 0).
- Then, you pick one of the two possible slopes for the flight and extend a line segment from your chosen point until the first time you hit the edge of a building or another flight. This segment must not end in the middle of the ground (though segments that end at floor 0 are allowed). This line segment is the new flight that you are going to build.
- Flights must be built only in the space between the buildings.
- All points on the new flight become connected to the ground and if this flight ends at the edge of a building, that floor of that building becomes connected to the ground.
For simplicity, you are only allowed to create flights whose length is a multiple of the square root of 2. That is, a flight connects a vertex of the grid in the first image to another vertex there. Below is an example of a final staircase configuration of valid flights:
The cost of a flight is determined by its length. You are given int[] cost containing Width elements. The i-th element in cost (0-based indexing) is the actual cost to build a flight whose length is (i+1) * SQRT(2). Note that the cost of the flight is the cost of the original length at the time it is built. Starting a new flight at some non-endpoint of an existing flight (for the purposes of this problem) does not divide the existing flight into two and does not affect the cost of the existing flight.
Return the minimum cost required to connect all the emergency exits to the ground.
