Stabbing Number

A histogram is a simple rectilinear polygon $H$, where the interior angle at each vertex is either $90^\circ$ or $270^\circ$. $H$ has a horizontal edge that sees every point $q$ inside $H$, including points on its interior and its boundary. An edge $e$ sees a point $q \in H$ if there is a vertical segment $s$ that connects $e$ to $q$ and lies inside $H$.

Let $H$ be a histogram with $n$ vertices, and let $R$ be a decomposition of $H$ into rectangles whose sides are vertical or horizontal. The vertices of the rectangles need not all be vertices of $H$. You may add extra vertices on the boundary of $H$, in its interior, or both.

The stabbing number of a horizontal or vertical segment $s$ inside $H$ with respect to $R$ is the number of rectangles in $R$ whose interior (not just their boundaries) $s$ intersects. The stabbing number of $R$ is the maximum stabbing number of any horizontal or vertical segment $s$ inside $H$. Compute a decomposition $R$ with the minimum stabbing number.

The first line contains two positive integers $m$ and $n$ ($1 \le m, n \le 50$), the number of rows and columns of the table that shows the histogram. Each of the next $m$ lines contains exactly $n$ characters. * marks the boundary of the histogram, and the rest of the table is filled with dots (.). Each edge of the histogram contains at least three * characters. The histogram has at least four and at most 16 edges, and no two edges overlap, intersect, or touch. In other words, each * is adjacent to exactly two other * characters.

Print the stabbing number of the given histogram on one line.