SP1267 ORIGLIFE - Origin of Life

康威的《生命游戏》并不是真正意义上的游戏，而是一种「细胞自动机」—— 它是一组用于描述网格中相邻细胞之间相互作用的规则。在这个游戏里，我们有一个 $n$ 行 $m$ 列的矩形网格，每个格子通过整数坐标 $(x, y)$ 唯一标识。游戏随着一系列步骤进行；每一步都会根据当前一代计算得出下一代。游戏以第一代开始。在任何一代中，每个细胞的状态要么是活的，要么是死的。在下一代中，每个细胞的状态可能会改变，这取决于当前代中与它相邻的细胞状态。两个细胞 $(x_1, y_1)$ 和 $(x_2, y_2)$ 如果水平、垂直或对角线相邻，即满足 $|x_1 - x_2| \leq 1$ 且 $|y_1 - y_2| \leq 1$，则被认为是直接邻居。不是边界上的每个细胞都有八个直接邻居。游戏的过程受三个整数参数 $(a, b, c)$ 影响，其规则如下： - 如果一个活细胞在当前代中拥有的活邻居少于 $a$ 个，它会因孤独而死去。那么在下一代中它是死的。 - 如果一个活细胞在当前代中拥有的活邻居多于 $b$ 个，它会因过度拥挤而死去。那么在下一代中它也是死的。 - 如果一个死细胞在当前代中有多于 $c$ 个活邻居，那么它将复活，也就是说在下一代中变为活细胞。 - 否则，细胞的状态在当前代和下一代间保持不变。 这一过程将无限进行下去。最终，某个世代可能会重复出现，这样游戏就会一直持续下去；或者所有细胞都会死亡。此外，如果我们往前追溯可能导致当前代的前几代，我们可能会发现其中有一代是无法通过规则从前一代生成的，这种世代被称为「伊甸园」。给定游戏的参数以及当前代的状态，你需要判断游戏是否可能从「伊甸园」开始。如果可以，请输出从「伊甸园」状态到达当前世代所需的最少步骤数。如果有多个答案，输出最小的那个；如果没有「伊甸园」，则输出 -1。

输入以一个整数开头，表示测试用例的数量。对于每个测试用例，会有 $m + 1$ 行输入。第一行包含游戏的五个整型参数 $m, n, a, b, c$，整数之间用空格分隔。约束条件为 $1 \leq m \leq 4$，$1 \leq n \leq 5$，$1 \leq a < b \leq 8$，$1 \leq c \leq 8$。接下来的 $m$ 行，每行包含一个长度为 $n$ 的字符串，表示当前代中的一行。在字符串中，星号（`*`）代表活细胞，点号（`.`）代表死细胞。测试用例之间没有空行。

对于每个测试用例，输出一个整数，表示从「伊甸园」状态达到输入状态所需的最少步骤数。如果不存在「伊甸园」，则输出 -1。 **本翻译由 AI 自动生成**