409734: GYM103714 D Ловушка
Description
Вы попали на одно поле с тиграми, которые так и хотят Вас съесть. Поле представляет собой прямоугольную таблицу $$$n \times m$$$. Некоторые клетки поля являются стенами и через них нельзя пройти.
Единственное, что Вас спасает на данный момент — все действия, Ваши и тигров, происходят пошагово. За один шаг Вы или тигр можете переместиться в соседнюю клетку вверх, вниз, влево, вправо или остаться на месте. Вы и тигры ходите по очереди. Сначала Вы совершаете один шаг, затем все тигры совершают по одному шагу.
Чтобы спастись, Вам необходимо добраться до любого края поля, не попавшись в лапы цепких тигров — именно там Вы видите телепорт в безопасное место. Тигры прекрасно Вас видят и всегда Вас преследуют. Самое главное не допустить коварного просчета, когда Вы окажетесь на одной клетке с тигром!
Формально, Вы сможете спастись, если существует маршрут к краю поля, такой что ни в один момент времени Вы и тигр не могли бы оказаться в одной ячейке. Краем поля считается любая ячейка, которая находиться на первой или последней строке поля, или на первом или последнем столбце.
Понимая безысходность ситуации, Вы пытаетесь просчитать возможный путь до любого из телепортов. Через некоторое время, известное лишь автору этой задачи, телепорты закроются, поэтому среди доступных для побега маршрутов, выбрать надо кратчайший. Есть возможность, что такого пути вообще не существует, поэтому единственным решением будет подавать сигналы $$$SOS$$$, пока Вас кто-нибудь не услышит.
Сможете ли Вы решить эту головоломку?
Входные данныеПервая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^3$$$) — размеры поля.
Следующие $$$n$$$ строк содержат по $$$m$$$ символов: '.' обозначает пустую клетку, '#' обозначает стену, 'P' обозначает клетку, в которой вы находитесь, 'T' обозначает клетку с тигром. Гарантируется, что поле содержит ровно один символ 'P'.
Выходные данныеЕсли Вы смогли решить головоломку, выведите $$$YES$$$ и отметьте маршрут на поле символами $$$P$$$. Если существует несколько маршрутов минимальной длины, по которым можно спастись, выберите любой. Если Ваши попытки оказались тщетными, выведите $$$SOS$$$.
ПримерыВходные данные4 5 ...T. ..#.# #.P.# .####Выходные данные
YES ...T. PP#.# #PP.# .####Входные данные
4 5 ..T.. ..#.# #.P.# .####Выходные данные
SOSВходные данные
3 2 T# P# ##Выходные данные
YES T# P# ##Входные данные
3 3 T## .P# ###Выходные данные
SOS