5057: Cleaner Robot
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
J. Cleaner Robot
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Masha has recently bought a cleaner robot, it can clean a floor without anybody's assistance.
Schematically Masha's room is a rectangle, consisting of w×h square cells of size 1×1. Each cell of the room is either empty (represented by character '.'), or occupied by furniture (represented by character '*').
A cleaner robot fully occupies one free cell. Also the robot has a current direction (one of four options), we will say that it looks in this direction.
The algorithm for the robot to move and clean the floor in the room is as follows:
You know the position of furniture in Masha's room, the initial position and the direction of the cleaner robot. Can you calculate the total area of the room that the robot will clean if it works infinitely?
Schematically Masha's room is a rectangle, consisting of w×h square cells of size 1×1. Each cell of the room is either empty (represented by character '.'), or occupied by furniture (represented by character '*').
A cleaner robot fully occupies one free cell. Also the robot has a current direction (one of four options), we will say that it looks in this direction.
The algorithm for the robot to move and clean the floor in the room is as follows:
- clean the current cell which a cleaner robot is in;
- if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1;
- otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2.
You know the position of furniture in Masha's room, the initial position and the direction of the cleaner robot. Can you calculate the total area of the room that the robot will clean if it works infinitely?
Input
The first line of the input contains two integers, w and h (1≤w,h≤10)− the sizes of Masha's room.
Next w lines contain h characters each− the desc
It is guaranteed that in the given w lines letter 'U', 'R', 'D' or 'L' occurs exactly once. The cell where the robot initially stands is empty (doesn't have any furniture).
Output
In the first line of the output print a single integer− the total area of the room that the robot will clean if it works infinitely.
Examples
Input
2 3 U.. .*.
Output
4
Input
4 4 R... .**. .**. ....
Output
12
Input
3 4 ***D ..*. *...
Output
6
Note
In the first sample the robot first tries to move upwards, it can't do it, so it turns right. Then it makes two steps to the right, meets a wall and turns downwards. It moves down, unfortunately tries moving left and locks itself moving from cell (1,3) to cell (2,3) and back. The cells visited by the robot are marked gray on the picture.
输入样例 复制
输出样例 复制