Problem Statement |
| | You work in the field of Robotics and you are doing some black-box testing. Two robots, Robbie and Speedy, are randomly placed in a rectangular room, which is divided into xSize * ySize cells. Each robot receives a few movement commands that are executed one by one, at the same time, by both the robots.
A move is represented by an uppercase letter, which is one of the following:
- 'U': the robot moves from the coordinates (x, y) to the coordinates (x - 1, y). This command is ignored when x = 0.
- 'D': the robot moves from the coordinates (x, y) to the coordinates (x + 1, y). This command is ignored when x = xSize - 1.
- 'L': the robot moves from the coordinates (x, y) to the coordinates (x, y - 1). This command is ignored when y = 0.
- 'R': the robot moves from the coordinates (x, y) to the coordinates (x, y + 1). This command is ignored when y = ySize - 1.
Two robots may collide if they start one of their turns from the same cell, end one of their turns in the same cell, or exchange positions at one of their turns. You will be given an int xSize and an int ySize denoting the dimensions of the rectangular room, a String commandsRobbie denoting the movement commands given to Robbie and a String commandsSpeedy denoting the movement commands given to Speedy. Your task is to return the probability that the two robots will collide, taking into acount every possible start position for both of the robots. The probability for each robot to start in any specific cell is the same for all cells.
|
| |
Definition |
| | | Class: | RobotCollision | | Method: | probability | | Parameters: | int, int, String, String | | Returns: | double | | Method signature: | double probability(int xSize, int ySize, String commandsRobbie, String commandsSpeedy) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Your return value must have an absolute or relative error less than 1e-9. |
| |
Constraints |
| - | xSize will be between 1 and 100, inclusive. |
| - | ySize will be between 1 and 100, inclusive. |
| - | commandsRobbie and commandsSpeedy will each contain between 0 and 10 characters, inclusive. |
| - | Each character in commandsRobbie and commandsSpeedy is either 'U', 'D', 'L' or 'R'. |
| - | commandsRobbie and commandsSpeedy have the same length. |
| |
Examples |
| 0) | |
| | | Returns: 0.27 | In this example, Robbie goes one step left and Speedy goes one step right. Out of the 100 possible starting positions (10 for each robot), 27 of them will lead to collision. A collision happens in one of the following three ways:
- Robbie and Speedy start at the same cell. In this case we have an instant collision. There are 10 such starting positions.
- Robbie starts at Speedy's immediate right. In this case we have a frontal collision as the two robots approach each other. There are 9 such starting positions.
- Robbie starts two steps to the right from Speedy. In this case the robots end up in the same cell after they make their moves, so again, we have a collision. There are 8 such starting positions. |
|
|
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |