만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

다이아몬드

면접 대비

시간 제한1초메모리 제한512 MB

요약
n행 m열 표에서 가장자리가 #이고 안쪽이 모두 .인 다이아몬드의 개수를 셉니다.
난이도

보통10점 중 5점

유형
행렬, 동적 계획법, 누적 합
정답자
아직 제출이 없습니다

문제

Lovro는 nn 행 mm 열의 표를 가지고 있으며, 각 칸은 . 또는 # 중 하나입니다. 정사각형을 45° 회전하면 표 안에 다이아몬드 모양이 만들어집니다. 표의 일부가 다이아몬드로 인정되려면 가장자리가 모두 # 문자로 이루어져야 하고, 내부는 모두 .으로 채워져 있어야 하며, 비어 있지 않아야 합니다. 다이아몬드 바깥의 문자는 무엇이든 상관없습니다. 다이아몬드에는 여러 크기가 있으며, 가장 작은 다이아몬드 세 개는 첫 번째 예제에 나와 있습니다.

Fabijan은 Lovro에게 표에 다이아몬드가 몇 개 있는지 세어 달라고 부탁했습니다. 세지 못하면 Lovro가 쿠키를 주어야 합니다. 표에 있는 다이아몬드의 개수를 세는 프로그램을 작성하세요.

입력

첫 줄에 양의 정수 nn과 mm (1≤n,m≤20001 \le n, m \le 2000)이 주어집니다. 각각 행의 수와 열의 수입니다. 이어지는 nn개의 줄에는 표를 나타내는 . 또는 # 문자가 각각 mm개씩 주어집니다.

출력

표에 있는 다이아몬드의 개수를 한 줄에 출력합니다.

힌트

두 번째 예제에 대한 설명입니다. 표에 다이아몬드는 하나뿐이며, 가능한 가장 작은 크기입니다. 이를 포함하는 다른 도형이 있어 보이지만, 내부가 .으로 모두 채워져 있지 않아 다이아몬드가 아닙니다. 표 오른쪽의 도형도 가장자리에 #이 빠져 있어 다이아몬드가 아닙니다.

예제3

  1. 예제 1

    입력
    7 25
    .#...#....#....#.....#...
    #.#..#...#.#...#....#.#..
    .#...#..#...#..#...#...#.
    .....#...#.#...#..#.....#
    .....#....#....#...#...#.
    .....#.........#....#.#..
    .....#.........#.....#...
    
    예상 출력
    3
    
  2. 예제 2

    입력
    11 17
    .....#........#..
    ....#.#........#.
    ...#...#....#...#
    ..#.....#....#.#.
    .#....#..#....#..
    #....#.#..#......
    .#....#..#.......
    ..#.....#........
    ...#...#.........
    ....#.#..........
    .....#...........
    
    예상 출력
    1
    
  3. 예제 3

    입력
    5 11
    ##.#.#.#.##
    #.#.#.#.#.#
    .#.#.#.#.#.
    #.#.#.#.#.#
    ##.#.#.#.##
    
    예상 출력
    14