심판의 바코드

교통 체증에 갇혀 있다가, 옆 택시에 붙은 흥미로운 식당 광고를 발견한다. 광고에는 2차원 바코드가 새겨져 있어 휴대폰으로 사진을 찍으니, 휴대폰이 코드를 읽어 가장 가까운 매장까지의 지도가 있는 웹 주소를 알려 준다.[1]

2차원 바코드의 "이미지"가 주어질 때, 그것이 나타내는 문자열을 알아내야 한다.

2차원 바코드는 고정된 부분과 가변 부분으로 이루어진다. 아래 그림에서 고정 칸은 0 또는 1로, 가변(데이터) 칸은 -로 표시한다.

1010---01
1000---00
10-------
10-------
10-------
1000---00
101000001

가변 칸이 데이터를 담는다. 바코드가 위 그림과 같은 방향(7행 9열, 즉 데이터 칸 30개)일 때, 데이터 칸은 왼쪽에서 오른쪽, 위에서 아래 순서로 읽는다.

예를 들어 다음 바코드가 주어지면,

101000101
100011000
100100010
101101011
100111011
100011000
101000001

순서대로 읽은 데이터 비트는 다음과 같다.

001110010001011010110111011110

이를 5비트씩 끊는다.

00111 00100 01011 01011 01110 11110

각 묶음을 십진수로 바꾼다.

7 4 11 11 14 30

마지막으로 아래 표에 따라 각 값을 문자로 해독한다.

따라서 이 바코드는 hello!로 해독된다. 모든 바코드는 정확히 6개의 문자를 담는다(데이터 비트 30개 ÷ 5 = 6).

첫 줄에는 데이터 집합의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어진다.

각 데이터 집합은 H W 형태의 줄로 시작하며, $H$ ($7 \le H \le 80$)와 $W$ ($9 \le W \le 80$)는 각각 이미지의 높이와 너비이다. 이어서 $H$개의 줄이 주어지고, 각 줄에는 카메라가 촬영한 흑백 이미지를 나타내는 $W$개의 이진 숫자(0 또는 1)가 있다.

이미지에 바코드가 있다면 정면으로 반듯하게 촬영되어 있지만, 90도의 배수만큼 회전되어 있을 수 있다.

각 데이터 집합마다 한 줄을 출력한다.

• 이미지에 유효한 바코드가 정확히 하나 있으면, 그 해독 값을 출력한다.
• 유효한 바코드가 하나도 없으면 NOCODE를 출력한다.
• 유효한 바코드가 둘 이상이어서 진짜 바코드를 가려낼 수 없으면 INTERFERENCE를 출력한다.

[1] Rekimoto, Jun and Ayatsuka, Yuji. 2000. CyberCode: Designing Augmented Reality Environments with Visual Tags. Sony Computer Science Laboratories, Inc.