Under construction

Still being built. Things may change

Dijamant

Interview

Time limit1sMemory limit512 MB

Summary
Count the diamonds in an n by m table of '.' and '#' characters, where each diamond has a border of '#' and an interior of only '.'.
Level

Medium5 of 10

Topics
Matrix, Dynamic programming, Prefix sum
Solved
No attempts yet

Problem

Lovro has a table of nn rows and mm columns, where each cell is either . or #. When a square is rotated by 45°, a diamond shape is formed. For a part of the table to count as a diamond, its edge must consist only of the character #, 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. The three smallest diamonds are shown in the first sample.

Fabijan asked Lovro to count the diamonds in the table, or else Lovro has to give him a cookie. Write a program that counts the number of diamonds in his table.

Input

The first line contains positive integers nn and mm (1≤n,m≤20001 \le n, m \le 2000), the number of rows and columns. Each of the next nn lines contains mm characters . or #, describing the table.

Output

Print the number of diamonds in the table on the only line.

Hint

Clarification of the second example: there is only one diamond in the table, the smallest possible one. Another shape appears to contain it, but it is not 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 its edge is missing a #.

Examples3

  1. Example 1

    Input
    7 25
.#...#....#....#.....#...
#.#..#...#.#...#....#.#..
.#...#..#...#..#...#...#.
.....#...#.#...#..#.....#
.....#....#....#...#...#.
.....#.........#....#.#..
.....#.........#.....#...
    Expected output
    3

  2. Example 2

    Input
    11 17
.....#........#..
....#.#........#.
...#...#....#...#
..#.....#....#.#.
.#....#..#....#..
#....#.#..#......
.#....#..#.......
..#.....#........
...#...#.........
....#.#..........
.....#...........
    Expected output
    1

  3. Example 3

    Input
    5 11
##.#.#.#.##
#.#.#.#.#.#
.#.#.#.#.#.
#.#.#.#.#.#
##.#.#.#.##
    Expected output
    14