Patisserie ACM

Time limit1sMemory limit128 MB

Summary
Given a hole-free connected polyomino of # cells, find the minimum number of axis-aligned rectangles whose union is exactly the shape, cutting only along grid lines.
Level

Medium7 of 10

Topics
Dynamic programming, Matrix, Implementation, Geometry
Solved
No attempts yet

Problem

Amber, a pastry chef, opened her own shop last month. To promote it she decided to enter the International Chocolate Patissier Competition, where she has been perfecting a recipe for sweet chocolate bars. After thousands of attempts she finally nailed the recipe. Shaping the chocolate into a neat rectangle, however, takes great skill, and this time she ended up with another oddly shaped bar like the one in Figure G-1.

Figure G-1

Figure G-1: A strangely shaped chocolate bar

Each chocolate bar is made of many small rectangular chocolate segments. Adjacent segments are separated by a groove so they can be snapped apart easily. Amber wants to cut each oddly shaped bar into rectangular pieces to sell in her shop, following these rules:

  • Every cut must run along a groove.
  • Every resulting piece must be rectangular.
  • The bar must be split into as few pieces as possible.

Under these rules, Figure G-2 is a valid way to cut the bar in Figure G-1. Figures G-3 and G-4 are invalid: G-3 leaves a non-rectangular piece, and G-4 produces more pieces than G-2.

Figure G-2

Figure G-2: A cutting that obeys the rules

Figure G-3

Figure G-3: A cutting that leaves a non-rectangular piece

Figure G-4

Figure G-4: A cutting that produces more pieces than Figure G-2

Write a program that computes the minimum number of pieces the bar is divided into when it is cut according to the rules.

Input

The input consists of several datasets, each describing one chocolate bar.

The first line of a dataset contains two integers hh and ww (2≤h≤1002 \le h \le 100, 2≤w≤1002 \le w \le 100), the height and width of the bar measured in segments. Each of the next hh lines contains ww characters describing one row of the grid. The character at row ii, column jj means:

  • # — a chocolate segment is present at that position;
  • . — no chocolate is present there.

Every dataset is guaranteed to describe a single connected bar with no holes: it never looks like the disconnected bars in Figure G-5 or the bars with holes in Figures G-6 and G-7, and it always contains at least one #.

Figure G-5

Figure G-5: Disconnected chocolate bars

Figure G-6

Figure G-6: A chocolate bar with a hole

Figure G-7

Figure G-7: Another chocolate bar with a hole

The end of the input is a line containing two zeros separated by a space; this line is not part of the data and must not be processed.

Output

For each dataset, output a single line containing one integer: the number of pieces produced when the bar is cut according to the rules. Print nothing else.

Examples1

  1. Example 1

    Input
    3 5
###.#
#####
###..
4 5
.#.##
.####
####.
##.#.
8 8
.#.#.#.#
########
.######.
########
.######.
########
.######.
########
8 8
.#.#.#.#
########
.##.#.#.
##....##
.##.###.
##...###
.##.###.
###.#.##
4 4
####
####
####
####
0 0
    Expected output
    3
5
11
19
1