프로그램화가

문제 정보

문제

가로 M픽셀, 세로 N픽셀로 구성된 그림 파일이 주어집니다. 이 그림 파일에는 집, 물고기, 새싹, 사탕, 그리고 왕관 패턴이 다양한 크기로 여러 개 그려져 있습니다. 아래에 각 패턴의 크기 1, 2, 3인 예제들이 주어집니다. 물론 그림에는 이보다 큰 패턴들도 그려져 있을 수 있습니다.

주어진 그림 파일에 각 패턴이 몇 개씩 그려져 있는지 계산하는 프로그램을 작성하세요.

각 그림 파일에는 90도, 180도, 270도 회전한 패턴들이 포함됩니다. :)

_____________________________
_______________________o_____
____________o_________o_o____
___o_______o_o_______o___o___
__o_o_____o___o_____o_____o__
_ooooo___ooooooo___ooooooooo_
__o_o_____o___o_____o_____o__
__ooo_____o___o_____o_____o__
__________ooooo_____o_____o__
____________________ooooooo__
_____________________________
집(house)
__________________________________________________
___________________________________oo__________oo_
________________oo______oo_______oo__oo______oo_o_
___oo__oo_____oo__oo__oo_o_____oo______oo__oo___o_
_oo__oo_o___oo______oo___o___oo__________oo_____o_
___oo__oo_____oo__oo__oo_o_____oo______oo__oo___o_
________________oo______oo_______oo__oo______oo_o_
___________________________________oo__________oo_
__________________________________________________
물고기(fish)
___________________________________
________________________ooo___ooo__
____________oo___oo____o___o_o___o_
__o___o____o__o_o__o________o______
_o_o_o_o_______o____________o______
____o__________o____________o______
____o__________o____________o______
___________________________________
새싹(sprout)
________________________________
_________________________oo_____
_____________oo_________o__o____
_o_oo_o___o_o__o_o___o_o____o_o_
_oo__oo___oo____oo___oo______oo_
_o_oo_o___o_o__o_o___o_o____o_o_
_____________oo_________o__o____
_________________________oo_____
________________________________
사탕(candy)
_________________________________________
_________________________oo___o___o___oo_
___________oo___o___oo___o_o_o_o_o_o_o_o_
_oo___oo___o_o_o_o_o_o___o__o___o___o__o_
_o_o_o_o___o__o___o__o___o_____________o_
_o__o__o___o_________o___o_____________o_
_o_____o___o_________o___o_____________o_
_o__o__o___o____o____o___o______o______o_
__oo_oo_____oooo_oooo_____oooooo_oooooo__
_________________________________________
왕관(crown)

입력

입력의 첫 줄에는 테스트 케이스의 수 C가 주어집니다. 각 테스트 케이스의 첫 줄에는 그림 파일의 높이 N과 너비 M이 주어집니다. 그 후 N줄에 각각 길이가 M인 문자열로 그림 파일의 각 가로 줄이 주어집니다. 문자열의 각 문자는 한 픽셀을 나타내며, 빈 칸을 나타내는 _와 패턴을 나타내는 o로 구성됩니다. 모든 o는 정확히 하나의 패턴에 속합니다. 어떤 두 패턴도 상하좌우나 대각선으로 인접하지 않습니다. 하지만 하나의 패턴 내부에 다른 패턴이 들어갈 수는 있습니다.

출력

각 테스트 케이스마다 한 줄에 패턴의 이름과 개수를 아래 예제처럼 출력하세요. “house fish sprout candy crown”의 순서가 바뀌면 안 됩니다.

예제 입력

2
15 19
_____________oo__oo
_o___o_____oo__oo_o
o_o_o_o______oo__oo
___o_____o_________
___o____o_o________
_______ooooo_______
________o_o________
________ooo________
___________________
_____oo____oo___oo_
__o_o__o_o_o_o_o_o_
__oo____oo_o__o__o_
__o_o__o_o_o_____o_
_____oo____o__o__o_
____________oo_oo__
8 15
_ooooo___ooooo_
o_____o_o_____o
_______o_______
_______o_______
_______o_______
_______o_______
_______o_______
_______o_______

예제 출력

house 1 fish 1 sprout 1 candy 1 crown 1
house 0 fish 0 sprout 1 candy 0 crown 0

노트

10 ≤ N, M ≤ 100

2개의 댓글이 있습니다.