← 返回题目列表

Codeforces · 374/C

C. 伊娜和迪玛

中文机器翻译题面 查看原题

Inna和Dima在店里买了一张n×m大小的桌子。表的每个单元格包含一个字母:“D”、“I”、“M”、“A”。

Inna 爱 Dima,所以她想在桌子上移动时尽可能多地重复他的名字。为此,Inna 的行为如下:

1. 最初,Inna 选择表格中写有字母“D”的某个单元格;
2. 然后 Inna 可以移动到某个包含字母“I”的侧面相邻的表格单元格;然后,她可以从该单元格转到包含书面字母“M”的侧面相邻表格单元格之一;然后她可以转到包含字母“A”的侧面相邻单元格。然后,伊娜认为她已经记下了她爱人的名字;
3. Inna 的下一步行动可以是转到包含字母“D”的侧面相邻表格单元格之一,然后以类似的方式继续遍历名称 DIMA。伊娜从不漏掉任何一个字母。因此,从字母“D”她总是转到字母“I”,从字母“I”她总是转到字母“M”,从字母“M”她总是转到字母“A”,从字母“A”她总是转到字母“D”。

根据初始表格单元格的选择,Inna 可以无限次或某个正的有限次数查看姓名 DIMA,或者她一次不能查看他的名字。帮助 Inna 找出她可以重复名字 DIMA 的最大次数。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 103)。

然后接下来的 n 行描述了 Inna 和 Dima 的桌子。每行包含 m 个字符。每个字符是以下四个字符之一:“D”、“I”、“M”、“A”。

请注意,不保证该表至少包含一个字母“D”。

输出

如果 Inna 无法一次输入名字 DIMA,则打印一行“Poor Dima!”没有引号。如果 DIMA Inna 可以输入无限多个名字,请打印“Poor Inna!”没有引号。否则打印一个整数——Inna 可以遍历名称 DIMA 的最大次数。

示例

输入 #1

1 2
DI

输出 #1

Poor Dima!

输入 #2

2 2
MA
ID

输出 #2

Poor Inna!

输入 #3

5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID

输出 #3

4

注意

样品注释:

在第一个测试样本中,Inna 无法单次访问名称 DIMA。

在第二个测试样本中,Inna 可以遍历无限多个单词 DIMA。为此,她应该从右下角开始按顺时针方向移动。

在第三个测试示例中,最佳策略是从表格左上角的单元格开始。从这个单元格开始,Inna 可以使用 DIMA 这个名字四次。