Задача №111709. Тупики в городе
Компания, в которой все ещё работает ваш друг, решила выпустить новую игру для мобильных телефонов, чтобы пассажирам было не так скучно стоять в пробках. Зная вас как хорошего программиста, вам поручили написать основную часть этой игры.
Игра будет состоять в том, что игрок будет управлять автобусом, перемещающимся по городу. В первой версии игры город будет представлять собой прямоугольное поле размера N * M клеток, каждая из которых либо занята зданием, либо свободна (т. е. по ней проходит дорога). Автобус игрока может перемещаться лишь по дорогам, но не по зданиям.
Кроме того, автобус считается достаточно большим, настолько, что он не может разворачиваться в пределах одной клетки. Правда, вам пока не хочется учитывать конкретные размеры автобуса, поэтому для простоты игроку будет запрещено делать два хода подряд в противоположных направлениях, а любые другие маневры будут разрешены.
Таким образом, каждым очередным ходом игрок может переместить автобус на любую соседнюю по стороне свободную клетку, кроме той, с которой автобус только что приехал. (Первым ходом можно переместить автобус в любую сторону.)
В результате понятно, что автобус игрока может застрять в тупике, откуда ему будет некуда двигаться. Более того, ясно, что есть клетки, куда заезжать нельзя, т. к., заехав туда, в итоге игрок будет вынужден доехать до тупика. Строго говоря, пусть игрок перемещает автобус бесконечно долго (т. е. в течение бесконечного количества ходов). Тогда несложно видеть, что в некоторых свободных клетках игрок может бывать бесконечно много раз (при условии, что начальная клетка выбрана удачно), а в некоторых — не более одного (и то лишь в начальной части игры). Сейчас вы хотите написать программу, которая разделит все свободные клетки поля на эти два типа.
На первой строке входного файла находятся два числа N и M — количество строк и столбцов игрового поля соответственно (1 ≤ N, M ≤ 500). Далее следуют N строк, описывающих поле. В каждой строке находятся ровно M символов, каждый из которых может быть или ‘#’ (решётка, ASCII-код 35), или ‘.’ (точка). Решётка обозначает клетку со зданием, точка — свободную клетку.
В выходной файл выведите N строк по M символов в каждой: для клеток, в которых находятся здания, выводите ‘#’, для клеток, где игрок может побывать не более одного раза — ‘X’ (латинская заглавная буква X), для остальных клеток — ‘.’.
4 12 .#....#.##.. .##.#.#.##.. ......####.. .##.#.#.####
X#X...#X##.. X##.#.#X##.. XXX...####.. X##X#X#X####
3 2 ## ## ##
## ## ##