Escape the Maze

Interview

Time limit1sMemory limit512 MB

Summary

Each cell holds a direction to the next cell; count how many starting cells eventually leave the N by M grid.

Level: Medium5 of 10
Topics: Graph, DFS, Implementation, Simulation
Solved: No attempts yet

Problem

There is a maze of size N×M, divided into cells of size 1×1. Each cell contains one character, and the character determines which cell you move to next.

If the character in cell (r, c) is

U, you must move to (r-1, c).
R, you must move to (r, c+1).
D, you must move to (r+1, c).
L, you must move to (r, c-1).

Count the number of cells from which the maze can be escaped. A cell is escapable if, starting from that cell and moving according to the characters, you eventually move outside the boundary of the maze.

Input

The first line gives the size of the maze, N and M (3 ≤ N, M ≤ 500). The next N lines give the character written in each cell of the maze.

Output

Print the number of cells from which the maze can be escaped.

Examples4

Example 1
Input
```
3 3
DDD
DDD
DDD
```
Expected output
```
9
```
Example 2
Input
```
3 3
DDR
DLU
LLL
```
Expected output
```
9
```
Example 3
Input
```
3 3
RRD
RDD
ULL
```
Expected output
```
0
```
Example 4
Input
```
3 4
RRDD
RRDR
DULU
```
Expected output
```
4
```