| Codeforces Round 607 (Div. 1) |
|---|
| Закончено |
Вы всемогущее существо и создали прямоугольный мир. Ваш мир настолько удобный, что может быть представлен в виде таблицы размером $$$r \times c$$$. Каждая клетка этой таблицы обозначает некоторую страну. Каждая страна принадлежит некоторой религии. Всего существует две религии в этом мире. Одна из религий называется Beingawesomeism, люди этой религии делают добрые поступки, чтобы быть хорошими. Другая религия называется Pushingittoofarism, люди этой религии совершают убийства, чтобы быть плохими.
На самом деле вы не абсолютно всемогущи. У вас есть только одна сила, которую вы можете применить бесконечное число раз! Ваша сила позволяет вам посылать миссионерские группы. Когда миссионерская группа из определенной страны, назовем ее $$$a$$$, приходит в другую страну $$$b$$$, она меняет религию страны $$$b$$$ на религию страны $$$a$$$.
Силу можно использовать следующим образом:
- Вы выбираете горизонтальную полоску $$$1 \times x$$$ или вертикальную полоску $$$x \times 1$$$ внутри таблицы. Вы можете выбирать любое значение $$$x$$$;
- Вы выбираете направление $$$d$$$. Если вы выбрали горизонтальную полоску, вы можете выбрать направления СЕВЕР или ЮГ. Если вы выбрали вертикальную полоску, вы можете выбрать направления ВОСТОК или ЗАПАД;
- Вы выбираете количество шагов $$$s$$$;
- Вы командуете каждой стране находящейся внутри выбранной полоски послать миссионерскую группу, которая пройдет $$$s$$$ шагов в направлении $$$d$$$. На каждом шаге, она посетит и возможно поменяет религию (способом описанным ранее) у всех $$$s$$$ стран на своем пути;
- параметры $$$x$$$, $$$d$$$, $$$s$$$ можно выбирать такими, чтобы никакая миссионерская группа не вышла за пределы таблицы.
Следующая картинка показывает один возможный способ использования силы. Здесь символ A обозначает страну с религией Beingawesomeism и символ P обозначает страну с религией Pushingittoofarism. Здесь мы выбрали горизонтальную полоску $$$1 \times 4$$$, направление СЕВЕР и количество шагов $$$s = 2$$$.
Вы существо, которое верит в свободную волю каждого человека. Однако, вы хотите немедленно приостановить убийства. Таким образом вы решили использовать силу и попробовать сделать Beingawesomeism религией всех стран.
Какое минимальное количество применений силы требуется, чтобы сделать религией каждой страны Beingawesomeism?
Если это сделать невозможно, вы должны признать свой провал и сообщить об этом.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$), количество тестовых случаев. В следующих строках находится описание тестовых случаев.
Первая строка каждого тестового случая содержит два целых числа $$$r$$$ и $$$c$$$, обозначающие размеры таблицы ($$$1 \le r, c \le 60$$$). Следующие $$$r$$$ строк содержат по $$$c$$$ символов, описывающих религии стран. $$$j$$$-й символ в $$$i$$$-й строке описывает религию страны в строке $$$i$$$ и столбце $$$j$$$. При этом:
- символ «A» означает, что религия Beingawesomeism;
- символ «P» означает, что религия Pushingittoofarism.
Гарантируется, что все символы таблицы это «A» или «P». Гарантируется, что сумма $$$r \cdot c$$$ по всем тестовым случаям не превосходит $$$3 \cdot 10^6$$$.
Для каждого тестового случая, выведите единственную строку, содержащую минимальное возможное количество использований силы нужное, чтобы сделать Beingawesomeism религией во всех странах. Если сделать Beingawesomeism религией во всех странах невозможно, выведите строку «MORTAL» (без кавычек).
4 7 8 AAPAAAAA PPPPAAAA PPPPAAAA APAAPPPP APAPPAPP AAAAPPAP AAAAPPAA 6 5 AAAAA AAAAA AAPAA AAPAP AAAPP AAAPP 4 4 PPPP PPPP PPPP PPPP 3 4 PPPP PAAP PPPP
2 1 MORTAL 4
В первом тестовом случае можно добиться требуемого за два применения силы.
Первое использование:
Второе использование:
Во втором тестовом случае можно добиться требуемого за одно применение силы.
В третьем тестовом случае невозможно сделать религией всех стран Beingawesomeism, поэтому ответ «MORTAL».
