생명의 기원

콘웨이의 생명 게임(Game of Life)은 사실 게임이 아니라 셀 자동자(cellular automaton), 즉 격자 위에서 서로 인접한 칸들이 어떻게 상호작용하는지를 정하는 규칙의 모음입니다. 여기서는 $m$개의 행과 $n$개의 열로 이루어진 직사각형 격자를 다루며, 각 칸은 정수 좌표로 구분됩니다.

게임은 이산적인 단계로 진행됩니다. 현재 세대로부터 다음 세대가 계산됩니다. 모든 세대에서 각 칸은 살아 있음(live) 또는 죽어 있음(dead) 중 하나의 상태를 가집니다. 어떤 칸의 다음 세대 상태는 현재 세대에서 그 칸의 이웃들의 상태에만 의존합니다. 서로 다른 두 칸 $(x_1, y_1)$과 $(x_2, y_2)$는 $|x_1 - x_2| \le 1$이고 $|y_1 - y_2| \le 1$일 때 이웃입니다. 즉, 가로·세로·대각선으로 맞닿은 칸들이 서로 이웃이며, 격자의 경계에 있지 않은 칸은 이웃이 여덟 개입니다.

세 정수 매개변수 $a$, $b$, $c$가 상태 전이 규칙을 결정합니다.

• 살아 있는 칸의 살아 있는 이웃이 $a$개보다 적으면 외로움으로 죽습니다(다음 세대에서 죽어 있음).
• 살아 있는 칸의 살아 있는 이웃이 $b$개보다 많으면 과밀로 죽습니다(다음 세대에서 죽어 있음).
• 죽어 있는 칸의 살아 있는 이웃이 $c$개보다 많으면 태어납니다(다음 세대에서 살아 있음).
• 그 밖의 경우 칸의 상태는 그대로 유지됩니다.

규칙을 계속 적용하면 언젠가 이전에 나왔던 세대가 다시 나타나(생명이 영원히 이어짐) 반복되거나, 모든 칸이 죽을 수 있습니다. 반대로 과거로 거슬러 올라가 보면, 어떤 세대는 그것을 한 단계 만에 만들어 낼 수 있는 이전 세대가 전혀 존재하지 않을 수 있습니다. 이런 세대를 에덴 동산(Garden of Eden)이라고 부릅니다.

매개변수와 현재 세대가 주어질 때, 그 역사가 에덴 동산에서 시작되었을 수 있는지 판정하세요. 가능하다면, 어떤 에덴 동산에서 출발하여 현재 세대에 도달하는 데 필요한 최소 단계 수를 출력합니다. 현재 세대 자체가 에덴 동산이면 단계 수는 $0$입니다. 현재 세대로 이어지는 에덴 동산이 존재하지 않으면 -1을 출력합니다.

출력은 정수 하나입니다.

첫째 줄에 공백으로 구분된 다섯 개의 정수 $m$, $n$, $a$, $b$, $c$가 주어집니다. 제약은 $1 \le m \le 4$, $1 \le n \le 5$, $1 \le a < b \le 8$, $1 \le c \le 8$입니다.

이어지는 $m$개의 줄에는 각각 현재 세대의 한 행을 나타내는 $n$개의 문자로 이루어진 문자열이 주어집니다. 문자열에서 *는 살아 있는 칸을, .은 죽어 있는 칸을 나타냅니다.