에필 게임

컴퓨터 과학 수업을 들어 본 사람이라면 거의 누구나 존 콘웨이의 세포 자동자인 "라이프 게임(Game of Life)"을 알고 있습니다. 탄생, 생존, 죽음이라는 매우 단순한 규칙만으로도 놀라운 복잡성이 생겨납니다.

게임은 직사각형 격자 위에서 진행되며, 각 칸은 여덟 개의 이웃(인접한 칸)을 가집니다. 각 칸은 살아 있거나(occupied) 비어 있습니다(empty). 다음 세대는 이전 세대로부터 다음 규칙에 따라 만들어집니다.

• 살아 있는 칸의 살아 있는 이웃이 0, 1, 4, 5, 6, 7, 8개이면 그 칸은 죽습니다(0 또는 1: 외로움, 4에서 8까지: 과밀).
• 살아 있는 칸의 살아 있는 이웃이 둘 또는 셋이면 그 칸은 다음 세대까지 생존합니다.
• 비어 있는 칸의 살아 있는 이웃이 정확히 셋이면 그 칸은 살아 있는 칸이 됩니다(탄생).

오랫동안 연구된 문제 중 하나는 "에덴의 동산(Garden of Eden)" 배치, 즉 어떤 이전 배치에 규칙을 적용해도 나올 수 없는 배치의 존재 여부입니다. 우리는 이를 확장하여 "에필 게임(Game of Efil)"을 생각합니다. 어떤 배치가 주어졌을 때, 그 배치의 바로 이전 배치가 될 수 있는 배치는 몇 개일까요(부모 배치의 개수)? 격자를 유한하게 유지하기 위해, 격자는 원환면(토러스)으로 다룹니다. 즉 위쪽 끝과 아래쪽 끝이 서로 맞닿아 감기고, 왼쪽 끝과 오른쪽 끝도 서로 맞닿아 감깁니다.

한 칸의 이웃을 셀 때, 감김(wrap-around) 때문에 어떤 칸이 두 방향 이상에서 인접하게 되면 그 칸은 여러 번 세어질 수 있으며, 아주 작은 격자에서는 한 칸이 자기 자신을 이웃으로 셀 수도 있습니다. 그러한 경우는 모두 각각 세어집니다.

여러 개의 테스트 케이스가 있습니다. 각 케이스는 두 양의 정수 m과 n이 적힌 줄로 시작하며, 이는 배치의 행 수와 열 수입니다. 다음 줄에는 살아 있는 칸의 개수인 음이 아닌 정수 k가 주어집니다. 이어지는 k개의 줄에는 각각 살아 있는 한 칸의 행과 열이 주어지며, 행과 열의 번호는 0부터 시작합니다. 입력은 m = n = 0인 줄로 끝나며, 이 줄은 처리하지 않습니다. m과 n의 곱은 16 이하라고 가정해도 됩니다.

각 테스트 케이스마다, 케이스 번호와 가능한 부모 배치의 개수를 Case X: N possible ancestors. 형식으로 한 줄에 출력합니다. 여기서 X는 케이스 번호(1부터 시작)이고 N은 그 개수입니다. 가능한 부모 배치가 하나도 없으면 대신 Case X: Garden of Eden.을 출력합니다.