eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

В изначально пустой прямоугольник разрешается ставить пять звездочек в ряд по вертикали или горизонтали, не выходя при этом за границы прямоугольника. При этом различные пятерки звездочек имеют право пересекаться и налегать друг на друга. Вам дано расположение звездочек в прямоугольнике. Можно ли его получить по указанным правилам, и если можно, то какое минимальное количество пятерок звездочек надо поставить, чтобы его получить? \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}, если данную конфигурацию получить невозможно. В противном случае выведите наименьшее число пятерок звездочек, с помощью которого можно получить данную конфигурацию.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
5 6
.*....
.*****
.*....
*****.
.*....
Çıxış verilənləri #1
3
Müəllif Михаил Дворкин
Mənbə Зимняя школа, Харьков 2011, День 3