A very simple robot moves in a random cardinal or diagonal direction (cardinal directions are north, south, east and west, and diagonal directions are north-east, north-west, south-east, and south-west) each timestep. Thus, the robot has a 12.5% chance of trying to move in each of 8 directions. If the robot moves in a diagonal direction, it moves one unit left or right, and then one unit up or down (both in the same timestep), depending on the direction. If the robot moves in a cardinal direction, it moves 1 unit in that direction. Given a String[], floor representing a bird's eye view of the floor, you are to determine the probability that the robot will end up at location (x,y) after time timesteps. You should return the probability as truncated parts per 1000. In other words, if act is the actual probability, return (int)(act*1000). Each character in floor represents one square unit of the floor and is an 'X', an 'R' or a '.', representing an obstacle, a robot, or an open floor, respectively. There is only one robot, and if it attempts to move into a square occupied by an obstacle, or it attempts to move diagonally when there is an obstacle in either of the locations that it is moving between it instead does not move. More specifically, the robot may move diagonally, if and only if the locations that it moves between and to are clear. Also, the robot can not move outside of the floor. In other words, consider floor to be surrounded by obstacles. Location (x,y) is represented by character x of element y of floor.
|