토러스 위의 생명 게임
면접 대비시간 제한2초메모리 제한512 MB
양끝이 이어진 8x8 격자에서 콘웨이 라이프를 돌려, 일시적인 과정 이후 최종 반복 주기를 계산합니다.
문제
콘웨이의 생명 게임을 m × n개의 정사각형 칸으로 이루어진 토러스에서 한다. m × n 토러스는 m × n 직사각형의 왼쪽 변과 오른쪽 변, 위쪽 변과 아래쪽 변을 각각 붙여 만든 도형이다. 각 칸은 행 번호와 열 번호를 나타내는 좌표 (r, c)로 구분한다. 모든 칸은 죽어 있거나 살아 있다. 게임의 상태는 토러스 위에서 살아 있는 칸과 죽어 있는 칸이 이루는 배치다.
토러스 위의 모든 칸에는 가로, 세로, 대각선으로 인접한 정확히 8개의 이웃 칸이 있다. 특히 칸 (1, 1)의 이웃은 (0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)이다. 칸 (0, 1)의 이웃은 (m, 0), (m, 1), (m, 2), (0, 0), (0, 2), (2, 0), (2, 1), (2, 2)이다.
시간이 한 단계 지날 때마다 게임의 상태가 바뀐다. i + 1 단계에서 각 칸의 상태는 i 단계에서 그 칸의 이웃 8개의 상태에 따라 다음 규칙으로 정해진다.
- i 단계에서 그 칸의 이웃 중 살아 있는 칸이 1개 이하이면, i + 1 단계에서 그 칸은 죽는다.
- i 단계에서 그 칸의 이웃 중 살아 있는 칸이 2개이면, i + 1 단계에서 그 칸의 상태는 i 단계와 같다.
- i 단계에서 그 칸의 이웃 중 살아 있는 칸이 3개이면, i + 1 단계에서 그 칸은 살아난다.
- i 단계에서 그 칸의 이웃 중 살아 있는 칸이 4개 이상이면, i + 1 단계에서 그 칸은 죽는다.
처음 상태를 이 계의 씨앗이라고 한다. k ∈ N∗에 대해, 게임이 어떤 상태에 있을 때 정확히 k 단계 뒤에 다시 같은 상태로 돌아오면 그 상태는 주기 k를 가진다고 한다. 예를 들어 그림 2의 왼쪽 배치는 주기가 2이다. 한 단계 뒤에 오른쪽 배치가 되고, 다시 한 단계 뒤에 왼쪽 배치가 된다.
주어진 씨앗에 대해, 이 씨앗의 주기는 게임이 이 씨앗에서 시작해 언젠가 주기 k인 상태에 도달하게 하는 가장 작은 k ∈ N∗이다. 씨앗이 주어졌을 때 이 계의 주기를 구하시오.
입력
입력은 여러 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 주어진다. 각 테스트 케이스가 이어진다. 테스트 케이스의 첫 줄에는 공백 하나로 구분된 두 양의 정수 3 ≤ m ≤ 8과 3 ≤ n ≤ 8이 주어진다. m은 토러스의 행 수, n은 열 수이다. 다음 m개 줄은 씨앗을 나타낸다. 각 줄은 한 행을 나타내며 정확히 n개의 문자로 이루어지고, 각 문자는 죽은 칸을 나타내는 'x' 또는 살아 있는 칸을 나타내는 'o'이다.
출력
입력의 각 테스트 케이스마다 한 줄을 출력한다. 이 줄에는 주어진 씨앗의 주기를 나타내는 양의 정수 p > 0이 들어간다. 출력에 빈 줄이 있어서는 안 된다.
힌트
그림 2: 예제 입력의 두 번째 테스트 케이스에 대한 그림. 주기가 2인 씨앗과 그것이 이끄는 배치