Задачи
Пятизвёздочная задача
Пятизвёздочная задача
В изначально пустой прямоугольник разрешается ставить пять звездочек в ряд по вертикали или горизонтали, не выходя при этом за границы прямоугольника. При этом различные пятерки звездочек имеют право пересекаться и налегать друг на друга.
Вам дано расположение звездочек в прямоугольнике. Можно ли его получить по указанным правилам, и если можно, то какое минимальное количество пятерок звездочек надо поставить, чтобы его получить?
\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
5 6 .*.... .***** .*.... *****. .*....
Выходные данные #1
3