Floor Decoration

Interview

Time limit2sMemory limit128 MB

Summary
Count the number of wooden planks by counting maximal runs of consecutive '-' in each row and '|' in each column of a grid.
Level

Easy2 of 10

Topics
Matrix, Implementation, Simulation
Solved
No attempts yet

Problem

Hyeongtaek is an architect who designed the floor decoration for Gihoon's room. The floor is a rectangle divided into square cells parallel to the walls, and each cell contains either - or |.

Each wooden plank has width 1 and a positive integer length. Adjacent - cells in the same row belong to one horizontal plank. Adjacent | cells in the same column belong to one vertical plank.

Given the floor pattern, determine how many wooden planks are needed.

Input

The first line contains two natural numbers N and M, the height and width of the floor.

Each of the next N lines contains a string of length M. These strings describe the floor pattern and consist only of - and |.

Both N and M are at most 50.

Output

Print the number of wooden planks needed.

Examples5

  1. Example 1

    Input
    4 4
----
----
----
----
    Expected output
    4

  2. Example 2

    Input
    6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-
    Expected output
    31

  3. Example 3

    Input
    7 8
--------
|------|
||----||
|||--|||
||----||
|------|
--------
    Expected output
    13

  4. Example 4

    Input
    10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||
    Expected output
    41

  5. Example 5

    Input
    6 6
-||--|
||||||
|||-|-
-||||-
||||-|
||-||-
    Expected output
    19