문자 인식
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
DCinside에 알고리즘 갤러리가 생겼다! 그러나 알고리즘 갤러리는 수많은 수갤러스(수능 갤러리 유저)들의 공격을 받곤 했는데, 수학 I 교과목에서 가장 쉬운 부분이 알고리즘을 다루는 부분이기 때문이라고 한다.
이를 보고 화가 난 algospot.com 멤버들은 알고리즘 갤러리에 CAPTZHA(Completely Automated Public Turing test to tell Zzizilies and Humans Apart) 라는 독자적인 글 등록 시스템을 개발하여 제공하였는데, 이 시스템의 유일한 문제는 알고리즘을 아는 사람들조차 사용하기 어려웠다는 데 있다.
여하튼, 좋은 구분 알고리즘을 만들었으니 뚫는 프로그램을 만들어 배포하면 자신의 명성이 높아지리라 생각한 당신은 프로그램의 개발에 착수하였다.
CAPTZHA는 찌질이와 사람을 구별하기 위하여 R행 C열의 흑백 격자 이미지를 사용한다. 하얀 바탕에 까만 색 점들이 모여 0에서 9 사이의 디지털 숫자를 표현한다. 각 숫자의 기본적인 모양은 아래와 같다.
*** * *** *** * * *** *** *** *** ***
* * * * * * * * * * * * * *
* * * *** *** *** *** *** * *** ***
* * * * * * * * * * * * *
*** * *** *** * *** *** * *** ***
이와 같은 문자들이 격자판에 여럿 표현되면, 그들의 합을 알아내어 적으면 된다. 문자들은 바로 옆에 인접하지 않으므로 연속된 검은 색 격자칸들의 집합이 어떠한 문자도 표현하지 않는 잘못된 경우는 존재하지 않는다. 그러나 이와 같은 방식은 너무 단순하기 때문에, 각 문자는 선분의 길이를 조절하여 변형될 수 있다. 예를 들어,
*
와 같은 문자는 1을 의미하며,
**
*
*
******
*
************
와 같은 문자는 2를 의미한다. 이러한 변형의 유일한 제약은 일반적인 형태에서 교점을 갖지 않는 두 선분이 인접해서는 안 된다는 점이다. 예를 들어
**
***
*
****
은 3이 아니라 잘못된 표현이다.
주어진 격자들로부터 나타난 모든 숫자들의 합을 알아내는 프로그램을 작성하여라.
입력
입력의 첫 행에는 정수 T (1 <= T <= 100)이 주어진다. 이 정수는 테스트 케이스의 수를 의미한다.
다음 행부터 T 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 행에는 정수 R과 C (1 <= R <= 24, 1 <= C <= 80) 가 주어진다.
다음 R 개의 행에 걸쳐 C 개의 문자가 주어지는데, 각 문자는 _ 혹은 *이다. _은 흰색 격자를 의미하며, *은 검은 색 격자를 의미한다.
출력
각 테스트 케이스에 대해, 주어진 격자들로부터 나타난 모든 숫자들의 합을 한 행에 하나씩 출력한다.
예제 입력
2 5 5 _____ _***_ _*_*_ _***_ _____ 10 15 _______________ _*__**_*_***_*_ _*___*___*_*_*_ _*___*_*_***_*_ _____*_*_____*_ _*****_*******_ _*___________*_ _**__********__ ____________*__ _______________
예제 출력
0 15
노트
