Window Shopping

Time limit1sMemory limit1024 MB

Summary

Choose some empty cells as shops so that the most edges separate a shop from a hallway, where a hallway is an empty cell reachable from both escalators.

Level: Medium7 of 10
Topics: Graph, BFS, Matrix
Solved: No attempts yet

Problem

You are helping a newly built shopping mall design its floor layout. The mall is a rectangular grid of cells. Two cells are adjacent if they share an edge. Each cell is empty, a pillar, or an escalator. There are exactly two escalators: one goes up and the other goes down. The escalators are small, so customers can walk through their cells freely without changing floors.

You choose some of the empty cells to build shops. The remaining empty cells and the two escalator cells are walkable for customers. An empty cell that is reachable from both escalators through walkable cells becomes a hallway. A shop window can be installed on an edge between a shop and a hallway.

After the layout is finished, some empty cells may still be unreachable from both escalators. These cells are not hallways, so no windows can be installed around them. An escalator is not a hallway either, so no window can be installed on any side of an escalator.

A recent customer analysis report shows that the mall's profit grows in proportion to the number of windows inside it. Find the maximum number of shop windows that can be installed.

Input

The first line contains two positive integers $r$ and $c$ ( $4 \le r \cdot c \le 99$ ), the number of rows and columns of the grid. Each of the next $r$ lines contains a string of length $c$ . Each character is one of the following:

. an empty cell
# a pillar
U the Up escalator (exactly one)
D the Down escalator (exactly one)

It is guaranteed that initially all empty cells are reachable from both escalators.

Output

Print a single integer, the maximum number of windows the mall can accommodate.

Hint

This is one optimal way to install windows in the first sample case. The blue cells are shops, and the red edges are windows.

Examples3

Example 1
Input
```
4 5
.....
#U...
...#.
...D.
```
Expected output
```
13
```
Example 2
Input
```
4 4
..#U
..#D
..#.
....
```
Expected output
```
5
```
Example 3
Input
```
3 2
##
.D
U.
```
Expected output
```
0
```