eolymp
bolt
Try our new interface for solving problems
Problems

Five-star challenge

Five-star challenge

In the initially empty rectangle is allowed to put five stars in a row vertically or horizontally, without exceeding the boundaries of the rectangle. In this case, five different stars have the right to cross and overlap each other. You are given the location of stars in the rectangle. Can I get it on these rules, and if so, what minimum number of fives stars should be put to get it? \InputFile The first line of the input file contains two integers \textbf{m} and \textbf{n} - the height and width of the rectangle (\textbf{1} ≤ \textbf{m} ≤ \textbf{5}; \textbf{1} ≤ \textbf{n} ≤ \textbf{10}). In each of the next \textbf{m} lines contain \textbf{n} characters of "\textbf{*}" and "\textbf{.}" corresponding to the asterisk and an empty cage. \OutputFile Derive \textbf{-1} if this configuration can not be obtained. Otherwise, output the smallest number of fives stars, with which you can get this configuration.
Time limit 1 second
Memory limit 256 MiB
Input example #1
5 6
.*....
.*****
.*....
*****.
.*....
Output example #1
3
Author Michael Dworkin
Source Winter School, Kharkov, 2011, Day 3