만드는 중입니다

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

테트리스 조각 세기

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

요약
회전만 허용되는 다섯 가지 테트로미노 모양이 격자에 각각 몇 번 나타나는지 세는 문제로, 인접한 도형은 서로 다른 색을 가진다.
난이도

보통10점 중 6점

유형
구현, 그래프, BFS, 완전 탐색
정답자
아직 제출이 없습니다

문제

이비차는 컴퓨터 게임을 만들고 있다. 지금까지 만든 부분은 테트리스 조각 다섯 종류를 격자에 놓는 기능이다. 조각은 격자에 놓기 전에 90도 단위로 원하는 횟수만큼 회전할 수 있고, 색을 칠할 수 있다. 뒤집기는 없다. 조각이 격자 밖으로 나가거나 이미 놓인 조각과 겹치면 놓을 수 없다.

다섯 가지 조각은 다음과 같다.

1번 조각2번 조각3번 조각4번 조각5번 조각

같은 그림을 문자로 적으면 아래와 같다. #는 조각이 차지하는 칸이다.

1번    2번     3번    4번    5번
##     ####    .##    ##.    .#.
##             ##.    .##    ###

3번 조각과 4번 조각은 서로 거울상이므로, 아무리 회전해도 겹치지 않는 서로 다른 조각이다.

이비차가 학교에 간 사이에 동생 마리차가 게임을 실행해서 조각을 마음대로 회전하고 색칠해 격자에 놓았다. 인접한 두 조각은 색이 서로 다르다. 두 조각은 변을 맞대고 있거나 꼭짓점만 닿아도 인접한 것으로 본다.

이비차가 돌아와 보니 동생이 놓은 조각이 그대로 남아 있다. 격자에 각 조각이 몇 개씩 놓여 있는지 구하라.

입력

첫째 줄에 격자의 행 개수 NN과 열 개수 MM이 주어진다 (1≤N,M≤101 \le N, M \le 10). 다음 NN개 줄에는 격자의 한 행이 MM개의 문자로 주어진다.

각 문자는 빈칸을 뜻하는 .이거나 조각의 일부를 뜻하는 영어 소문자다. 서로 다른 문자는 서로 다른 색을 뜻하고, 한 조각에 속한 네 칸은 모두 같은 문자다.

출력

정확히 다섯 줄을 출력한다. ii번째 줄에는 ii번 조각이 격자에 놓인 개수를 출력한다.

힌트

세 번째 예제의 격자를 그림으로 나타내면 다음과 같다.

예제3

  1. 예제 1

    입력
    4 5
    aaaa.
    .bb..
    .bbxx
    ...xx
    
    예상 출력
    2
    1
    0
    0
    0
    
  2. 예제 2

    입력
    4 5
    .aab.
    aabb.
    .cbaa
    cccaa
    
    예상 출력
    1
    0
    1
    1
    1
    
  3. 예제 3

    입력
    5 7
    .c.....
    ccdddd.
    caabbcc
    aabbacc
    ...aaa.
    
    예상 출력
    1
    1
    2
    1
    1