문자 인식

문제 정보

문제

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

노트

6개의 댓글이 있습니다.