만드는 중입니다

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

석공의 표식

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

요약
잡음이 섞인 흑백 사진에서 석재에 새겨진 세 가지 석공 마크 A, B, C의 개수를 각각 셉니다.
난이도

보통10점 중 7점

유형
행렬, 그래프, 구현
정답자
아직 제출이 없습니다

문제

석공의 표식은 건물이나 다른 공공 건축물의 다듬은 돌에 자주 새겨진 기호다. 피터는 카메라를 들고 파리를 걷다가 Tour JeanSans-Peur의 벽에서 이런 표식을 발견한다. 모든 돌에는 A, B, C 중 하나의 표식이 새겨져 있고, 표식은 꽤 잘 보인다. 그는 흑백 사진을 찍고 다음을 관찰한다:

  • 사진에는 돌들이 나오며, 모든 돌에는 정확히 하나의 표식이 있다.
  • 모든 표식은 다음 모양 중 하나를 가진다. 여기서 xx와 yy는 임의의 양의 정수이며, 표식마다 다를 수 있다. 표식은 흰 픽셀로 둘러싸여 있고, 회전할 수 없다.

  • 사진에는 잡음이 있으며, 잡음은 주변 8개 픽셀이 모두 흰 검은 픽셀이다.
  • 검은 픽셀은 세 종류이며, 각각 잡음, 석공의 표식, 돌 주변 영역에 해당한다.
  • 모든 흰 픽셀은 돌의 표면에 속하고, 그중 일부는 표식의 내부에도 속한다.
  • 같은 돌의 표면에 속하면서 표식의 내부에는 속하지 않는 흰 픽셀들은 상하좌우 인접 관계로 모두 연결되어 있다. 다만 돌의 표면은 볼록하지 않을 수 있다.
  • 돌 주변 영역의 검은 픽셀들은 상하좌우 및 대각선 인접 관계로 연결되어 있다. 즉 돌 주변 영역의 검은 픽셀 어디에서든 인접한 8방향 픽셀로 움직여 다른 모든 그런 픽셀에 갈 수 있다. 사진 테두리의 모든 픽셀은 검은색이며 이 영역에 속한다.

입력

첫 줄에 두 정수 WW와 HH가 주어진다. 이어지는 HH개의 줄에는 각각 길이 WW인 문자열이 주어진다. 문자열은 .과 #으로 이루어진다. #은 검은 픽셀, .은 흰 픽셀을 뜻한다.

출력

A, B, C 표식을 가진 돌의 개수를 각각 공백으로 구분한 세 정수 AA, BB, CC로 한 줄에 출력한다.

제한

7≤W≤10007 \le W \le 1000;

9≤H≤10009 \le H \le 1000.

예제1

  1. 예제 1

    입력
    26 15
    ##########################
    ##........######......#..#
    #...###....#####..#......#
    #...#.#....####.........##
    #...###.....##....#####..#
    #...#.#.....#.....#####..#
    #...###.....#.....##.##..#
    #........#..#.#...#####..#
    #..###......#.....#####..#
    #..#........#...#.##.##..#
    #..#........#.....##.##..#
    #..#...#.#..#...#.##.##..#
    #..###......#............#
    ###....#....##....##.....#
    ##########################
    
    예상 출력
    1 1 0