Lovro has a table of rows and columns, where each cell is either .
or #
. By
rotating a square by a diamond shape is formed in the table. For a part of the
table to be considered a diamond, its edge must also consist only of the character #
,
while its inside must be completely filled with .
and it must be nonempty. Outside
of a diamond, any character is allowed. Diamonds come in different sizes, and the
three smallest examples of a diamond are shown in the first sample.
Fabijan asked Lovro to tell him how many diamonds are there in the table, or else Lovro has to give him a cookie. Help Lovro by writing a program which counts the number of diamonds in his table.
Input Specification
The first line contains positive integers and , the number of rows and columns.
Each of the next lines contains characters .
or #
which describe the table.
Output Specification
In the only line print the number of diamonds in the table.
Constraints
Subtask | Points | Constraints |
---|---|---|
No additional constraints. |
Sample Input 1
7 25
.#...#....#....#.....#...
#.#..#...#.#...#....#.#..
.#...#..#...#..#...#...#.
.....#...#.#...#..#.....#
.....#....#....#...#...#.
.....#.........#....#.#..
.....#.........#.....#...
Sample Output 1
3
Sample Input 2
11 17
.....#........#..
....#.#........#.
...#...#....#...#
..#.....#....#.#.
.#....#..#....#..
#....#.#..#......
.#....#..#.......
..#.....#........
...#...#.........
....#.#..........
.....#...........
Sample Output 2
1
Explanation for Sample Output 2
There is only one diamond in the table (the one with the smallest possible size). There appears to be another diamond containing it, but it is not considered a diamond because its inside is not completely filled with .
. The shape on the right side of the table is also not a diamond because it's missing a #
character on its edge.
Sample Input 3
5 11
##.#.#.#.##
#.#.#.#.#.#
.#.#.#.#.#.
#.#.#.#.#.#
##.#.#.#.##
Sample Output 3
14
Comments