Давка!
У вас есть игровая доска размером n×n. На некоторых клетках расположены препятствия, за исключением крайнего левого и крайнего правого столбцов, которые всегда свободны. В крайнем левом столбце находятся ваши n фишек, по одной в каждом ряду. Ваша задача — как можно быстрее переместить все фишки в крайний правый столбец. За один ход вы можете переместить каждую фишку на одну клетку в направлении N (север), S (юг), E (восток) или W (запад), либо оставить её на месте. Фишка не может перемещаться на клетку с препятствием, и две фишки не могут оказаться на одной и той же клетке в одном ходе. Все фишки перемещаются одновременно, поэтому одна фишка может занять клетку, которую покидает другая фишка в том же ходе.
Задача состоит в том, чтобы определить минимальное количество ходов, необходимых для перемещения всех фишек в правый столбец, учитывая n и расположение препятствий.
Входные данные
Каждый тест начинается с положительного целого числа n, обозначающего размер доски, где n ≤ 25. Далее следуют n строк, каждая из которых содержит n символов. Если j-й символ в i-й строке — это 'X', то на позиции i, j находится препятствие; если символ — '.', то препятствия нет.
Препятствия никогда не будут в 0-м или (n-1)-м столбце, и всегда будет хотя бы один свободный путь между этими столбцами. Ввод заканчивается строкой, содержащей одну 0.
Выходные данные
Для каждого теста выведите минимальное количество ходов, необходимых для перемещения всех фишек с левой стороны доски на правую.