Натиск!#6651
У вас є ігрова дошка розміром n \times n. Деякі клітинки містять перешкоди, за винятком крайньої лівої та крайньої правої колонок, які не містять перешкод. Крайня ліва колонка заповнена вашими фігурами, по на кожен рядок. Ваша мета — перемістити всі ваші фігури до крайньої правої колонки якомога швидше. За один хід ви можете перемістити кожну фігуру в напрямку N, S, E або W на одну клітинку, або залишити цю фігуру на місці. Фігура не може переміщатися на клітинку, що містить перешкоду, і дві фігури не можуть переміститися на одну і ту ж клітинку за один хід. Усі фігури рухаються одночасно, тому одна може переміститися на місце, яке зараз зайняте іншою фігурою, якщо ця фігура сама переміститься в інше місце одночасно.
Знаючи та перешкоди, визначте найменшу кількість ходів, необхідних для переміщення всіх ваших фігур на праву сторону дошки.
Кожен тестовий випадок починається з додатного цілого числа , що вказує на розмір ігрової дошки, при цьому n \le 25. Далі йде рядків, що містять по символів кожен. Якщо -й символ у -му рядку є 'X', то на позиції , дошки є перешкода; в іншому випадку цей символ буде '.', що означає відсутність перешкоди.
Ніколи не буде перешкоди в -й або (n-1)-й колонці, і завжди буде принаймні один шлях без перешкод між цими двома колонками. Рядок, що містить лише , завершить введення.
Для кожного тестового випадку виведіть мінімальну кількість ходів, необхідних для переміщення всіх фігур з лівої сторони дошки на праву сторону.
Приклад 1