Marss

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

요약

정사각 부분행렬 중 두 대각선은 검은 픽셀이고 나머지는 모두 흰 픽셀인 것의 개수를 센다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 행렬, 누적 합
정답자: 아직 제출이 없습니다

문제

Marslased kahtlustavad, et nende planeedil on tulnukate luuredroonid. Droonide leidmiseks tegid nad hulga aerofotosid. On teada, et droonid paistavad nendel fotodel ristikujulistena. Täpsemalt loevad marslased kahtlasteks $2 \times 2$ või suuremad ruudukujulised alad, mille diagonaalidel olevad pikselid on mustad ja kõik ülejäänud valged. Mõned kahtlaste alade näited on alloleval joonisel.

Kirjutada programm, mis leiab kahtlaste alade arvu antud fotol.

입력

Sisendi esimesel real on foto mõõtmed $N$ ja $M$ ( $1 \le N \le 2\\,000$ , $1 \le M \le 2\\,000$ ).

Järgmisel $N$ real on igaühel täpselt $M$ märki, kus '.' tähistab valget ja '#' musta pikselit.

출력

Väljastada üks täisarv: kahtlaste alade arv sisendis kirjeldatud fotol.

예제2

예제 1

입력

10 9
#...#.#.#
.#.#...#.
..#...#.#
.#.#....#
#...#..#.
.....##..
.....##..
#.#.#..#.
.#.#.##.#
###.###..

예상 출력

예제 2

입력

8 8
#......#
.#....#.
..#..#..
...##...
...##...
..#..#..
.#....#.
#......#

예상 출력