Повний склад
Гра починається на дошці розміром M×N, де деякі клітинки позначені як "перешкоди" (на рисунку нижче вони зображені темними квадратами). Гравець обирає початкову позицію для м'яча (позначеного суцільною сірою точкою) і напрямок руху (вгору, вниз, вліво або вправо). Після вибору напрямку м'яч рухається в цьому напрямку, поки не зіткнеться з перешкодою, краєм дошки або своєю ж траєкторією. Коли це відбувається, м'яч зупиняється. Потім гравець може вибрати інший напрямок, і м'яч знову рухатиметься за тим же принципом. Гра завершується, коли не можна зробити жодного легального ходу. Гравець виграє, якщо і тільки якщо траєкторія охоплює всі порожні клітинки на дошці. На рисунку нижче показано траєкторію, яка демонструє один зі способів виграти гру за 10 кроків.
Вам потрібно написати програму, яка, отримавши початкову конфігурацію дошки, обчислить мінімальну кількість кроків, необхідних для виграшу в грі.
Вхідні дані
Кожен тестовий випадок у вхідному файлі починається з двох цілих чисел m і n (1 ≤ m, n ≤ 30), що визначають розмір дошки. Наступні m рядків описують початкову конфігурацію дошки. Кожен рядок містить n символів: '*' або '.', що вказують, чи є відповідна клітинка перешкодою або порожньою. [Наприклад, дивіться нижче на вхідний файл, що відповідає випадку на рисунку вище.] Гарантується, що початкова дошка не повністю покрита перешкодами. Обробляйте до кінця файлу; немає спеціального маркера кінця даних.
Вихідні дані
Виведіть мінімальну кількість кроків, необхідних для покриття дошки. Формат виводу має бути таким: "Case", один пробіл, номер випадку, двокрапка і один пробіл, і одне ціле число, що вказує мінімальну кількість кроків для виграшу в грі, або якщо виграти неможливо, число -1. Не додавайте пробілів у кінці рядка.