#651

Lines(2)

Темы: [Обход в ширину]

В таблице из \(N\) строк и \(N\) столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

Входные данные

В первой строке находится число \(N\), в следующих \(N\) строках - по \(N\) символов. Символом точки обозначена свободная клетка, латинской заглавной \(O\) - шарик, \(@\) - исходное положение шарика, который должен двигаться, латинской заглавной \(X\) - конечное положение шарика. 2 <= \(N\) <= 250.

Выходные данные

В первой строке выводится \(Y\), если движение возможно, или \(N\), если нет. Если движение возможно, далее следует \(N\) строк по \(N\) символов - как и на вводе, но \(X\), а также все точки по пути заменяются плюсами +.

Примеры

Входные данные

2
@.
.X

Выходные данные

Y
@.
++

Входные данные

2
@O
OX

Выходные данные

#652

Удаление клеток

Темы: [Обход в глубину]

Из прямоугольного листа клетчатой бумаги (\(M\) строк, \(N\) столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

Входные данные

В первой строке находятся числа \(M\) и \(N\), в следующих \(M\) строках - по \(N\) символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= \(M\), \(N\) <= 100.

Выходные данные

Вывести одно число.

Примеры

Входные данные

5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

Выходные данные

#657

Путь коня

Темы: [Обход в ширину]

Дана шахматная доска, состоящая из \(N\)x\(N\) клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.

Входные данные

В первой строке задано число \(N\). В следующих \(N\) строках содержится по \(N\) символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, \(@\) - заданные клетки (таких символов два). 2 <= \(N\) <= 50.

Выходные данные

Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом \(@\).

Примеры

Входные данные

2
@.
.@

Выходные данные

Impossible

Входные данные

3
@..
...
..@

Выходные данные

@@.
..@
@.@

#658

Грядки

Темы: [Обход в глубину]

Прямоугольный садовый участок шириной \(N\) и длиной \(M\) метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные

В первой строке находятся числа \(N\) и \(M\) через пробел, далее идут \(N\) строк по \(M\) символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ \(N\), \(M\) ≤ 200.

Выходные данные

Вывести одно число - количество грядок на садовом участке.

Примеры

Входные данные

5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

Выходные данные

#669

Путь спелеолога

Темы: [Обход в ширину]

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N³ кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.

Ограничения: 1 <= N <= 30.

Входные данные

В первой строке содержится число N. Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: # - обозначает клетку, заполненную камнями, точка - свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.

Выходные данные

Вывести одно число - длину пути до поверхности.

Примеры

Ввод 1
3

###
###
.##

.#.
.#S
.#.

###
...
###
Вывод 1
6
Комментарий 1
Нужно спуститься на уровень вниз,
сделать два движения на запад,
подняться на уровень вверх,
сделать движение на юг,
подняться на уровень вверх.