CF374C Inna and Dima

Inna 和 Dima 在商店买了一个 $n \times m$ 的桌子。桌子的每个格子中都写着一个单独的字母：“D”、“I”、“M”、“A”中的某一个。 Inna 很爱 Dima，所以她希望在桌子上移动时能尽可能多地拼出他的名字。因此，Inna 这样行动： 1. 首先，Inna 可以选择桌子上任意一个写有字母 “D” 的格子作为起点； 2. 然后，Inna 可以移动到与当前格子相邻且写有字母 “I” 的格子；然后再移动到相邻且写有字母 “M” 的格子；再移动到相邻且写有字母 “A” 的格子。此时，Inna 就算成功拼写了一次喜欢人的名字； 3. 下一步，Inna 可以从与当前格子相邻且写有字母 “D” 的格子再继续重复拼写 “DIMA”。Inna 不能跳过任何字母。因此，她只能按顺序从 “D” 移动到 “I”，从 “I” 到 “M”，从 “M” 到 “A”，从 “A” 再到 “D”。 根据初始位置的选择，Inna 可能能无限多次，有限多次，或者一次都不能完整地拼写出名字 “DIMA”。请你帮 Inna 计算，在桌子上最多能完整拼写多少次 “DIMA”。

输入的第一行为两个正整数 $n$ 和 $m$，满足 $1 \leq n, m \leq 10^3$。 接下来 $n$ 行描述桌子的字符分布。每行包含 $m$ 个字符，每个字符为大写字母 “D”、“I”、“M”、“A” 中的某一个。 注意，桌面上不保证一定存在字母 “D”。

如果 Inna 一次都无法拼写出 “DIMA”，输出一行 “Poor Dima!”（不带引号）。 如果 Inna 可以无限次拼写 “DIMA”，输出一行 “Poor Inna!”（不带引号）。 否则，输出 Inna 最多能完整拼写 “DIMA” 的最大次数。

样例说明： 在第一个样例中，Inna 一次都无法完整拼写 “DIMA”。 在第二个样例中，Inna 可以无限次拼写 “DIMA”。为此，她只需从右下角顺时针绕圈走即可。 在第三个样例中，最优策略是从左上角的格子出发。在这个格子出发，Inna 最多可以完整拼写 “DIMA” 四次。 由 ChatGPT 5 翻译