Alexander’s fianceé has been kidnapped by his arch-enemy Blake, the dark wizard that lives across the Big Old Desert. In order to save her, he must cross this large body of land as fast as he can.
Deserts are basically sand and only have a few obstacles, but Big Old Desert isn’t a common desert. Along the way, Alexander will find four different types of terrain: boring plains, bottomless pits, treacherous lakes and high mountains. You can think of each of these terrain types as occupying a single unit of space.
Luckily, the Sand Goblins, a tribe that used to inhabit this desert, used to store some useful artefacts all over the place. These objects (namely planks, canoes and balloons) can easily be found in plains and can be used to traverse the difficult types of terrain.
Balloons are the most versatile artefact and can be used to cross mountains, lakes and pits. However, using a balloon to cross one of these obstacles takes six units of time. Planks can be used to cross over lakes and pits. Planks are very unstable and they take five units of time to be used. Canoes are the least useful but also the fastest. They can only be used to cross lakes and it takes four units of time to do it.
Plains are the easiest of the four types of terrains and can be traversed using only one unit of time. Entering or leaving a plain carrying an artefact takes one extra unit of time. This means it can take between one and three units of time to traverse a plain. Alexander can only carry one artifact at a time; picking and dropping artefacts does not take any extra time. You can also safely drop an artefact where another artefact already exists.
Imagine the following example:
Alexander could take the plank in the first plain, drop it in the second one, take the balloon and go over the two pits and the mountain, trade the balloon for the canoe and cross the lake using it. Dropping the canoe in the last plain. This would take 2 + 2 + 1 + 2 + 6 + 6 + 6 + 3 + 3 + 4 + 2 = 37 units of time. Or he could ignore the first plank, take the ballon to cross the pits and the mountain, drop the balloon, ignore the canoe and use the plank to cross the lake and drop it in the last plain. This would take 1 + 1 + 1 + 2 + 6 + 6 + 6 + 2 + 2 + 5 + 2 = 34 units of time.
Your task is to find the fastest way for Alexander to traverse the desert using a certain predetermined path with a length of S units of space. For each unit of space, you will know the type of terrain, and, in the case of plains, if there is an artifact there and its type.
The first line of the input will contain a single integer N with the number of problems in the input file. N lines will follow each one describing a single problem. These will contain S characters describing each unit of space:
_ underscore An empty plain c lowercase c A plain with a canoe p lowercase p A plain with a plank b lowercase b A plain with a balloon L uppercase L A lake P uppercase P A pit M uppercase M A mountain
One line for each problem with a single integer representing the number of time units needed to traverse the desert as fast as possible. You can assume it is always possible to reach the end of the path.
| 1 ≤ N ≤ 50 | Number of problems |
| 1 ≤ S ≤ 100,000 | Number of units of space |
2 p__bPPMcpL_ _b_M______M__
34 39
This document was translated from LATEX by HEVEA.
