만드는 중입니다

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

셰바의 아메바

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

요약
검은 픽셀마다 주변 여덟 칸 중 정확히 두 칸이 검은 픽셀일 때, 격자 위에 서로 닿지 않는 닫힌 고리의 개수를 센다.
난이도

보통10점 중 4점

유형
그래프, DFS
정답자
아직 제출이 없습니다

문제

셰바 아리바는 크라우드펀딩 모금에 성공해 통신 판매 생물 교재 회사를 차렸다. 회사 Sheba's Amoebas는 단세포 생물인 아메바 군집을 미리 배양해 둔 페트리 접시를 배송한다. 셰바는 접시마다 아메바가 몇 마리 들어 있는지 확인해야 한다. 접시마다 흑백 이미지가 있고, 이 이미지는 아메바 한 마리가 검은 픽셀로 이루어진 단순 닫힌 고리 하나로 보이도록 미리 처리한 것이다. 고리는 검은 픽셀의 극소 집합으로, 집합에 속한 픽셀 각각이 집합의 다른 픽셀 정확히 두 개와 인접한다. 여기서 인접은 픽셀의 변이나 꼭짓점을 공유한다는 뜻이다. 이미지의 검은 픽셀은 모두 어떤 고리에 속한다.

검은 픽셀과 흰 픽셀로 이루어진 직사각형 배열에서 닫힌 고리가 몇 개인지 세는 프로그램을 작성하라. 이미지 안의 두 닫힌 고리는 서로 닿지도 겹치지도 않는다. 이웃을 둘러싸 삼켜 버리는 식인 아메바 종이 있어서, 아메바 안에 아메바가 들어 있기도 한다. 예를 들어 그림 1의 두 이미지에는 각각 아메바가 네 마리씩 있다.

그림 1: 아메바가 네 마리씩 들어 있는 페트리 접시 두 개.

입력

첫 줄에 정수 mm과 nn이 주어진다. (1≤m,n≤1001 \le m, n \le 100)

다음 mm개의 줄에는 각각 문자 nn개가 주어진다. #은 검은 픽셀, .은 흰 픽셀을 뜻한다. 모든 검은 픽셀은 자신의 이웃 여덟 개 중 정확히 두 개가 검은 픽셀이다.

출력

입력에 있는 고리의 개수를 정수 하나로 출력한다.

예제2

  1. 예제 1

    입력
    12 12
    .##########.
    #..........#
    #..#...##..#
    #.##..#..#.#
    #......#.#.#
    #....#..#..#
    #...#.#....#
    #..#...#...#
    .#..#.#....#
    #....#.....#
    #.........#.
    .#########..
    
    예상 출력
    4
    
  2. 예제 2

    입력
    12 10
    .#####....
    #.....#...
    #..#..#...
    #.#.#.#...
    #..#..#...
    .#...#....
    ..###.....
    ......#...
    .##..#.#..
    #..#..#...
    .##.......
    ..........
    
    예상 출력
    4