Dinosaur Park X35926


Statement
 

pdf   zip

html

Dan Zynoulus is opening a dinosaur park in Meashara. His park takes some area on a parallelogram made of triangular segments, like on the picture below. Unfortunately, dinosaurs are dangerous beasts, and they could attack innocent people or other dinosaurs, unless blocked by an electric fence. Thus, he puts poles in some vertices of the triangles on the map, and each pair of poles which are next to each other is connected with an electric fence.

Dan has got a file containing the map of the area, but he does not remember how many different dinosaurs can fit into his zoo (remember that you cannot put two dinosaurs so that one of them can reach the other one, since they would fight). Please help him!

Input

The first row contains two numbers x and y, 1≤ x≤ 2012, 1≤ y≤ 2012. These two numbers determine the size of the parallelogram.

Each of following y rows contains x . and # characters. A # sign as j-th character of (i+1)-th row denotes a pole (the sample input corresponds to the picture above).

Output

Public test cases

  • Input

    7 6
.......
..#....
..###..
.###.#.
....##.
.......

    Output

    4
    • Information
    Author
    Eryk Kopczynski
    Language
    English
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++