P10487 Nightmare II

昨晚，小 erriyue 做了一个可怕的噩梦。他梦到自己和女朋友被困在一个大迷宫里。更可怕的是，迷宫里有两个鬼魂。它们会杀人。现在小 erriyue 想知道在鬼魂找到他们之前，他是否能找到他的女朋友。 假设小 erriyue 和他的女朋友可以向四个方向移动。在每一秒中，小 erriyue 可以移动 $3$ 步，而他的女朋友只能移动 $1$ 步。鬼魂是邪恶的，每一秒它们都会分裂成几部分，占领距离它们两步以内的网格，直到它们占领整个迷宫。你可以假设在每一秒钟，鬼魂首先分裂，然后小 erriyue 和他的女朋友开始移动，如果小 erriyue 或者他的女朋友到达一个有鬼魂的网格，他们就会死亡。 注意：新的鬼魂也可以像原来的鬼魂一样分裂。

输入以一个整数 $T(1 \le T \le 3)$ 开始，表示测试案例的数量。 每个测试案例以一行开头，包含两个整数 $n$ 和 $m$，表示迷宫的大小。$(1 < n, m < 800)$ 接下来的 $n$ 行描述了迷宫。每行包含 $m$ 个字符。字符可能是： - `.` 表示空地，所有人都可以走。 - `X` 表示墙，只有人类无法行走。 - `M` 表示小 erriyue。 - `G` 表示女朋友。 - `Z` 表示鬼魂。 保证迷宫中恰好有一个字母 `M`、一个字母 `G` 和两个字母 `Z`。

在一行中输出一个整数 $S$，表示如果他们能成功相遇，小 erriyue 和他的女朋友将在最短时间 $S$ 内相遇，或者输出 $-1$ 表示他们未能相遇。 翻译来自于：[ChatGPT](https://chatgpt.com/)