CF1280B Beingawesomeism

你是一个全能的存在，你创造了一个矩形世界。事实上，你的世界如此单调，以至于可以用一个 $r \times c$ 的网格来表示。网格上的每个格子代表一个国家，每个国家都有一种主导宗教。你的世界里只有两种宗教。一种叫做 Beingawesomeism，他们行善只是为了行善。另一种叫做 Pushingittoofarism，他们杀人只是为了作恶。 哦，其实你并不是全能的。你只有一种能力，但可以无限次使用！你的能力与传教团有关。当某个国家 $a$ 的传教团经过另一个国家 $b$ 时，会将 $b$ 的主导宗教改变为 $a$ 的主导宗教。 具体来说，你每次使用能力的过程如下： - 你选择一个水平的 $1 \times x$ 子网格或一个垂直的 $x \times 1$ 子网格，$x$ 的值由你决定； - 你选择一个方向 $d$。如果你选择的是水平子网格，方向可以是 NORTH 或 SOUTH；如果选择的是垂直子网格，方向可以是 EAST 或 WEST； - 你选择步数 $s$； - 你命令子网格中的每个国家派出传教团，向 $d$ 方向行进 $s$ 步。在每一步中，他们会经过（并实际改变）所有 $s$ 步内经过的国家的主导宗教，如上所述； - 参数 $x$、$d$、$s$ 必须选择得当，保证所有传教团不会离开网格。 下图展示了你能力的一次可能使用方式。图中，A 代表主导宗教为 Beingawesomeism 的国家，P 代表主导宗教为 Pushingittoofarism 的国家。这里我们选择了一个 $1 \times 4$ 的子网格，方向为 NORTH，步数 $s=2$。  你基本上相信自由意志。不过，你实在不想再收到以你名义进行的谋杀了。因此，你决定使用你的能力，试图让 Beingawesomeism 成为每个国家的主导宗教。 你需要计算，最少需要使用多少次你的能力，才能让所有国家都信仰 Beingawesomeism？ 对于神来说，没有什么是不可能的。但你也许不是神？如果无法让所有国家都信仰 Beingawesomeism，你也必须承认自己的凡人身份，并如实告知。

输入的第一行包含一个整数 $t$（$1 \le t \le 2\cdot 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个用空格分隔的整数 $r$ 和 $c$，表示网格的行数和列数（$1 \le r, c \le 60$）。接下来的 $r$ 行，每行包含 $c$ 个字符，描述各国的主导宗教。具体地，第 $i$ 行第 $j$ 个字符表示第 $i$ 行第 $j$ 列的国家： - “A” 表示主导宗教为 Beingawesomeism； - “P” 表示主导宗教为 Pushingittoofarism。 保证网格中只包含 “A” 或 “P” 字符。保证单个文件中所有 $r \cdot c$ 的总和不超过 $3 \cdot 10^6$。

对于每个测试用例，输出一行，表示将所有国家转化为 Beingawesomeism 所需的最小能力使用次数。如果无法实现，则输出字符串 “MORTAL”（不带引号）。

在第一个测试用例中，只需两次能力使用即可完成： 第一次使用：  第二次使用：  在第二个测试用例中，只需一次能力使用即可完成。 在第三个测试用例中，无法将所有国家转化为 Beingawesomeism，因此答案为 “MORTAL”。 由 ChatGPT 4.1 翻译