글리프 조판

현대 폰트는 크게 두 종류로 나뉩니다. 하나는 아웃라인 폰트로, 글리프(각 문자의 모양)를 곡선의 집합으로 수학적으로 정의합니다. 다른 하나는 비트맵 폰트로, 글리프를 픽셀 패턴으로 정의합니다. 폰트에는 커닝 쌍("AW"처럼 특정 글리프 쌍의 간격을 조정해 올바르게 배치되도록 하는 정보), 트래킹 힌트(글리프 사이 간격 관리), 안티에일리어싱 힌트(계단 현상이 있는 가장자리를 부드럽게 처리) 등 다양한 부가 정보가 함께 담기기도 합니다. 이처럼 현대 폰트는 단순한 도형의 모음 그 이상이며, 이를 올바르게 표시하는 일은 흔히 마주치는 프로그래밍 과제입니다.

이 문제에서는 비트맵 폰트와, 글리프 패킹이라고 부르는 간단한 조판 방식을 다룹니다. 핵심 아이디어는 글리프 사이에 가로 방향으로 최소 한 픽셀의 간격을 유지하면서 글리프를 최대한 촘촘하게 붙이는 것입니다. 예를 들어 로마자 "P"와 "J"의 글리프는 가로로 맞닿지 않는 선에서 최대한 가깝게 밀어 붙일 수 있습니다.

패킹이 끝난 뒤에는 서로 다른 글리프의 픽셀이 대각선이나 세로로는 인접할 수 있지만 가로로는 인접할 수 없습니다. 서로 다른 글리프의 두 픽셀은 바로 위아래에 놓일 수 있고 대각선으로 맞닿을 수도 있지만, 가로로 바로 옆 칸에 놓일 수는 없습니다.

글리프 패킹에는 유용한 성질이 있습니다. 폰트에 "장식적인" 글리프를 넣어 두면, 똑같이 단순한 패킹 과정만으로도 별도의 작업 없이 특수한 효과를 낼 수 있습니다.

다만 글리프 패킹에는 주의할 점도 있습니다. 하이픈 글리프 뒤에 밑줄 글리프가 오는 경우를 생각해 봅시다. "가로 한 픽셀 간격" 규칙만 적용하면, 두 글리프의 보이는 픽셀이 같은 행을 전혀 공유하지 않으므로 얼마든지 가깝게 붙어 버립니다. 그래서 무언가가 더 필요하며, 그것이 바로 글리프 내부의 힌트입니다. 이 문제에서 힌트는 "보이지 않는" 픽셀로 한정합니다. 이 픽셀은 패킹을 계산할 때는 픽셀로 취급되지만, 패킹 결과를 표시할 때는 그려지지 않습니다. 보이지 않는 픽셀로 각 글리프의 형태를 채워 두면 하이픈과 밑줄이 올바른 간격으로 패킹됩니다.

올바른 패킹의 형식적 정의는 다음과 같습니다.

1. 서로 다른 글리프의 어떤 픽셀도 가로로 바로 인접하지 않는 범위에서, 글리프를 최대한 가깝게 붙인다.
2. 임의의 두 글리프에 대해, 왼쪽 글리프의 어떤 높이의 픽셀이 그 높이에서 오른쪽 글리프의 어떤 픽셀보다 오른쪽에 위치하도록 패킹해서는 안 된다.

조건 2는 이렇게 상상하면 쉽습니다. 두 글리프가 작은 간격을 두고 나란히 놓여 있다고 합시다. 두 글리프를 서로 "밀어 붙일" 때, 조건 2는 두 글리프의 픽셀이 서로를 "통과"하지 못하도록 막습니다.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 패킹할 글리프 집합을 나타냅니다. 한 테스트 케이스 안의 모든 글리프는 높이가 같으며, 첫 줄의 정수 N이 그 높이를 나타냅니다. 이어지는 N개의 줄에 패킹할 글리프들이 주어집니다. 비어 있는 픽셀은 점 .으로, 보이는 픽셀은 해시 기호 #으로, 보이지 않는 픽셀은 숫자 0으로 나타냅니다. 이웃한 글리프는 공백 문자 한 열로 구분됩니다.

한 테스트 케이스에는 항상 둘 이상의 글리프가 있으며, 그중 적어도 하나의 글리프에는 보이는 픽셀이 하나 이상 있습니다. 모든 글리프는 가장 왼쪽 열과 가장 오른쪽 열 각각에 비어 있지 않은 픽셀을 하나 이상 가지며, 같은 테스트 케이스의 다른 글리프 중 적어도 하나와 같은 높이에 비어 있지 않은 픽셀을 하나 이상 가집니다. 글리프의 크기는 최소 1×1에서 최대 20×20이고, 한 테스트 케이스의 글리프 수는 최대 20개입니다. 입력은 N이 0인 줄로 끝나며, 이 종료용 케이스는 처리하지 않습니다.

각 테스트 케이스에 대해, 먼저 해당 테스트 케이스의 번호(1부터 시작)를 한 줄에 출력합니다. 그다음 글리프들을 올바르게 패킹한 결과를 출력하는데, 비어 있는 픽셀과 보이지 않는 픽셀은 모두 점 .으로, 보이는 픽셀은 해시 기호 #으로 나타냅니다. 가장 왼쪽 열과 가장 오른쪽 열이 모두 보이는 픽셀을 하나 이상 포함하도록, 앞뒤의 빈 열(보이는 픽셀이 하나도 없는 열)은 생략합니다.