eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пятизвёздочная задача

Пятизвёздочная задача

В изначально пустой прямоугольник разрешается ставить пять звездочек в ряд по вертикали или горизонтали, не выходя при этом за границы прямоугольника. При этом различные пятерки звездочек имеют право пересекаться и налегать друг на друга. Вам дано расположение звездочек в прямоугольнике. Можно ли его получить по указанным правилам, и если можно, то какое минимальное количество пятерок звездочек надо поставить, чтобы его получить? \InputFile В первой строке входного файла содержатся два числа \textbf{m} и \textbf{n} --- высота и ширина прямоугольника (\textbf{1} ≤ \textbf{m} ≤ \textbf{5}; \textbf{1} ≤ \textbf{n} ≤ \textbf{10}). В каждой из следующий \textbf{m} строк содержится по \textbf{n} символов "\textbf{*}" и "\textbf{.}", соответствующих звездочке и пустой клетке. \OutputFile Выведите \textbf{-1}, если данную конфигурацию получить невозможно. В противном случае выведите наименьшее число пятерок звездочек, с помощью которого можно получить данную конфигурацию.
Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
5 6
.*....
.*****
.*....
*****.
.*....
Выходные данные #1
3
Автор Михаил Дворкин
Источник Зимняя школа, Харьков 2011, День 3