Дана поле, состоящая из \(n\) строк и \(m\) столбцов. Каждая ячейка матрица либо свободна, либо занята. В одной из свободных клеток находится лаборатория. Все ячейки за границами поля заблокированы.
Сумасшедший робот сбежал из лаборатории. В данный момент он находится в некоторой свободной клетке. Вы можете послать ему одну из следующих команд: «идти вправо», «идти вниз», «идти влево» или «идти вверх». Каждая команда означает переход в соседнюю клетку в соответствующем направлении.
Однако, так как робот сумасшедший, он сделает что угодно, кроме выполнения команды. При получении команды, он выберет такое направление, что оно отличается от данного в команде, и ячейка в выбранном направлении не занята. Если есть такое направление, то он переместится в этом направлении. Иначе, он не сделает ничего.
Мы хотим привести робота обратно в лаборатории, чтобы его починить. Для каждой свободной клетке определите, можно ли заставить робота достичь лаборатории, если он начнет в этой клетке. То есть, после каждого шага работа можно будет послать такую команду, что какие бы направления робот ни выбирал, он окажется в лаборатории.
Выходные данные
На каждый набор входных данных найдите все свободные клетки, из которых можно заставить робота дойти до лаборатории. В заданном поле замените свободные клетки (обозначенные точкой) знаком плюса ('+') в тех клетках, из которых можно заставить робота дойти до лаборатории. Выведите получившееся поле.
Примечание
В первом наборе входных данных нет такой свободной клетки, из которой можно заставить робота дойти до лаборатории. Рассмотрим угловую клетку. Если послать любое направление, то робот перейдет в граничную клетку, которая не является углом. Теперь рассмотрим не угловую граничную клетку. Какое бы направление вы ни послали, робот всегда может выбрать такое другое направление, что он окажется в углу.
В последнем наборе входных данных можно посылать команду, которая противоположна направлению к лаборатории, чтобы у робота не было выбора кроме как двигаться к ней.