Codeforces Round 220 (Div. 2) |
---|
Закончено |
Инна и Дима купили в магазине табличку размера n × m. В каждой ячейке этой таблички записана одна из букв: «D», «I», «M», «A».
Инна любит Диму, поэтому она хочет, двигаясь по табличке, собрать его имя как можно больше раз. Для этого Инна действует следующим образом:
В зависимости от выбора первоначальной ячейки таблицы Инна может собрать слово DIMA либо бесконечное количество раз, либо некоторое положительное конечное количество раз, либо вообще не может собрать слово DIMA ни разу. Помогите Инне определить, какое максимальное количество раз она может собрать слово DIMA.
Первая строка входных данных содержит два целых числа n и m (1 ≤ n, m ≤ 103).
Далее следует n строк, описывающих таблицу Инны и Димы. Каждая строка содержит m символов. Каждый символ — это один из символов: «D», «I», «M», «A».
Обратите внимание, не гарантируется, что таблица содержит хотя бы одну букву «D».
Если Инна не может собрать ни одного слова DIMA, в единственной строке выведите «Poor Dima!» без кавычек. Если Инна может собрать бесконечное количество слов DIMA, выведите «Poor Inna!» без кавычек. Иначе выведите целое число — какое максимальное количество раз Инна сможет собрать слово DIMA.
1 2
DI
Poor Dima!
2 2
MA
ID
Poor Inna!
5 5
DIMAD
DIMAI
DIMAM
DDMAA
AAMID
4
Пояснения к примерам:
В первом тестовом примере, Инна не может собрать слово DIMA ни разу.
Во втором тестовом примере, Инна может собрать бесконечное количество слов DIMA. Для этого она должна двигаться по часовой стрелке, начиная от правого нижнего угла.
В третьем тестовом примере, выгоднее всего изначально выбрать ячейку в левом верхнем углу таблицы. Начиная от этой ячейки, можно собрать слово DIMA 4 раза.
Название |
---|