### Problem Statement

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.

### Definition

 Class: Robot Method: getProb Parameters: String[], int, int, int Returns: int Method signature: int getProb(String[] floor, int x, int y, int time) (be sure your method is public)

### Constraints

-floor has between 1 and 50 elements, inclusive.
-Each element of floor has between 1 and 50 characters, inclusive.
-Each element of floor has the same number of characters.
-Each character of each element of floor is either a '.', an 'R', or an 'X'.
-There is exactly one 'R' in floor.
-The input will not cause rounding errors. In other words, the actual double probability will not be within .000001 of .xxx000, where the x's represent digits, unless it is exactly 0.
-time will be between 0 and 1000, inclusive.
-x will be between 0 and the length of the first element of floor - 1.
-y will be between 0 and the length floor - 1.

### Examples

0)

 ```{"R.XX", "..XX", "..XX", "...."}``` `3` `3` `7`
`Returns: 1`
1)

 `{"RX","X."}` `1` `1` `10`
`Returns: 0`
 You can't go between those 2, on a diagonal
2)

 `{"RX","X."}` `0` `1` `1000`
`Returns: 0`
 You can't land on an 'X'
3)

 `{"R."}` `0` `0` `10`
`Returns: 528`
4)

 `{"RX"}` `1` `0` `10`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1583

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4497&pm=1583

lars2520

#### Problem categories:

Dynamic Programming, Simulation