You have to escape from a laboratory, and you have pills number of "shrinking pills" to help you. Your normal height is 100 units, but when you take one of these pills your height decreases by pspeed units each second. You keep shrinking until your height reaches zero or less, and at that moment, you instantly return to your normal height. For example, if you take a pill that reduces your height by 40 units per second at time 0, your height will be 60 at time 1, then 20 at time 2, and 100 again at time 3. Note that you will never be zero or less units tall. You can only take one pill at a time, and you can only take a pill when you are at your normal size.
There are doors in the laboratory that close downward from the ceiling to the floor. All the doors start closing immediately. Each door is door units
tall and drops down by dspeed units each second. For example, consider a door with a height of 200 units, and a closing speed of
150. The door will be 200 units from the floor at time 0, 50 units from the floor at time 1, and fully closed at time 2.
All movements are discrete and simultaneous. For example, suppose you are standing next to a door that is 200 units from the floor. The door's closing speed is 125, and your pill's shrinking speed is 25. You take the pill and move towards the door. In the next second, the door will be 75 (200-125) units from the floor, you will be 75 units tall and you will be standing right under the door. If you do not move again, the door will kill you in the next second. If you do move, you'll be on the other side of the door with a height of 50 units, and the door will be fully closed.
At each second, you can either stay where you are or move horizontally or vertically by one square. You will be given a map of the laboratory as a String, where '@' represents your starting square, 'E' the exit, '#' a wall, uppercase 'X' a door and ' ' (space) an empty square. The laboratory will be completely surrounded by walls.
You are given pills, the number of available pills, pspeed, the shrinking speed of the pills, dspeed, the closing speed of the doors, door, the height of each door, and lab, the map of the laboratory. Return the minimum number of seconds needed to escape from the laboratory, or -1 if it is not possible.