30294번 - Flea 다국어

문제

You have placed glues on each cells of an $N\times M$ grid to create a rectangular flea trap. Each glue has a weak direction; if a flea on the glue jumps towards its weak direction, the flea can jump out of the glue.

More precisely, each glue is represented by U, D, L, or R, meaning up, down, left, and right respectively.

Fleas can jump at most $K$ cells in one jump. If a flea jumps out of the rectangle, we say that the flea has escaped.

You became curious about how effective your trap is. If a flea that is placed on a cell of the trap can escape after consecutive jumps, we call the cell an escapable cell. Your task is to count the number of escapable cells.

입력

In the first line, the trap sizes $N,ドル $M$ and the jump limit $K$ are given, separated by spaces.

For the next $N$ lines, each line contains a string of length $M,ドル indicating the weak direction of each cell.

출력

Print the number of escapable cells.

제한

• $N,ドル $M,ドル and $K$ are integers.
• 1ドル\le N\le 2,円 000$
• 1ドル\le M\le 2,円 000$
• 1ドル\le K\le 2,円 000$
• Each string consists of U, D, L, or R.

힌트