Problem:


Patisserie ACM

Amber Claes Maes, a patissier,  opened her own shop last month.
She decided to submit her work to the International Chocolate
Patissier Competition to promote her shop, and she
was pursuing a recipe of sweet chocolate bars.
After thousands of trials, she finally reached the recipe.
However, the recipe required high skill levels to form chocolate to
an orderly rectangular shape.
Sadly, she has just made another strange-shaped chocolate bar as shown in
Figure G-1.

Figure G-1: A strange-shaped chocolate bar

Each chocolate bar consists of many small rectangular segments
of chocolate.  
Adjacent segments are separated with a groove in
between them for ease of snapping.
She planned to cut the strange-shaped chocolate bars into several
rectangular pieces and sell them in her shop.
She wants to cut each chocolate bar as follows.

  
The bar must be cut along grooves.

  
The bar must be cut into rectangular pieces.

  
The bar must be cut into as few pieces as possible.

Following the rules, Figure G-2 can be an instance of cutting of
the chocolate bar shown in Figure G-1.  Figures G-3 and G-4
do not meet the rules; Figure G-3 has
a non-rectangular piece, and Figure G-4 has more pieces
than Figure G-2.

Figure G-2: An instance of cutting that follows the rules

Figure G-3: An instance of cutting that leaves a non-rectangular piece

Figure G-4: An instance of cutting that yields more pieces than Figure G-2

Your job is to write a program that computes the number of pieces
of chocolate after cutting according to the rules.

Input

The input is a sequence of datasets.  The end of the input is indicated by
a line containing two zeros separated by a space.  Each dataset is
formatted as follows.

h w

r(1, 1) ... r(1, w)

r(2, 1) ... r(2, w)

...

r(h, 1) ... r(h, w)

The integers h and w are the lengths of the two orthogonal
dimensions of the chocolate, in number of segments.
You may assume that 2 ≤ h ≤ 100 and 2 ≤ w ≤ 100.
Each of the following h
lines consists of w characters, each is either a
"." or a "#".  The character
r(i, j) represents whether 
the chocolate segment exists at the position (i, j )
as follows.

  
".": There is no chocolate.

  
"#": There is a segment of chocolate.

You can assume that there is no dataset that represents
either multiple disconnected bars as depicted in Figure G-5
or a bar in a shape with hole(s) as depicted in Figure G-6
and G-7.  You can also assume that there is at least one "#"
character in each dataset.

Figure G-5: Disconnected chocolate bars

Figure G-6: A chocolate bar with a hole

Figure G-7: Another instance of a chocolate bar with a hole

Output

For each dataset, output a line containing the integer representing
the number of chocolate pieces obtained by cutting according to the rules.
No other characters are allowed in the output.

Sample Input

3 5
###.#
#####
###..
4 5
.#.##
.####
####.
##.#.
8 8
.#.#.#.#
########
.######.
########
.######.
########
.######.
########
8 8
.#.#.#.#
########
.##.#.#.
##....##
.##.###.
##...###
.##.###.
###.#.##
4 4
####
####
####
####
0 0

Output for the Sample Input

3
5
11
19
1



Sample input:
3 5
###.#
#####
###..
4 5
.#.##
.####
####.
##.#.
8 8
.#.#.#.#
########
.######.
########
.######.
########
.######.
########
8 8
.#.#.#.#
########
.##.#.#.
##....##
.##.###.
##...###
.##.###.
###.#.##
4 4
####
####
####
####
0 0


Sample output:
3
5
11
19
1

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
from collections import deque
while 1:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break

    R = [raw_input() for i in xrange(h)]

    conn = [[[] for i in xrange(w)] for i in xrange(h)]

    for i in xrange(h-1):
        for j in xrange(w-1):
            first = R[i][j:j+2]; second = R[i+1][j:j+2]

            # ????????¨???????¨????
            if first.count('#') + second.count('#') == 3:
                conn[i][j].append((i, j))

            # ??£?????¨???????¨????

            # .#        ##
            # ## ????????? .# ?????????????????´????????????
            if (first == '.#' and second == '##') or (first == '##' and second == '.#'):
                k = j
                # #.        #.        ##
                # ## ????????? #. ????????? #. ?????°??????????????§???????????????
                while k+1 < w and R[i][k+1] != '.' and R[i+1][k+1] != '.':
                    k += 1
                if k+1 < w and ((R[i][k+1] == '#') ^ (R[i+1][k+1] == '#')):
                    # #.        ##
                    # ## ????????? #. ????????????????????§(i, j)??¨(i, k)?????????
                    conn[i][j].append((i, k))
                    conn[i][k].append((i, j))

            # .#        #.
            # ## ????????? ## ?????????????????´????????????
            if first in ['.#', '#.'] and second == '##':
                k = i
                # ##        ##        ##
                # #. ????????? .. ????????? .# ?????°??????????????§???????????????
                while k+1 < h and R[k+1][j] != '.' and R[k+1][j+1] != '.':
                    k += 1
                if k+1 < h and ((R[k+1][j] == '#') ^ (R[k+1][j+1] == '#')):
                    # ##        ##
                    # .# ????????? #. ????????????????????§(i, j)??¨(k, j)?????????
                    conn[i][j].append((k, j))
                    conn[k][j].append((i, j))

    # ??£??????????????????????????????????¨????
    used = [[0]*w for i in xrange(h)]
    deq = deque()
    ans = 0
    for i in xrange(h):
        for j in xrange(w):
            if conn[i][j] and not used[i][j]:
                used[i][j] = 1
                deq.append((i, j))
                cnt = 0
                while deq:
                    u, v = deq.popleft()
                    for r, c in conn[u][v]:
                        if not used[r][c]:
                            used[r][c] = 1
                            deq.append((r, c))
                    cnt += 1
                ans += (cnt + 1) / 2
    print ans + 1

Submission status: Accepted

Solution code:
# encoding: utf-8

# Dinic algorithm
from collections import deque
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

while 1:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break

    R = [raw_input() for i in xrange(h)]

    conn = [[0 for i in xrange(w)] for i in xrange(h)]

    P = []
    Q = []
    dep = 0

    for i in xrange(h-1):
        for j in xrange(w-1):
            # ??£?????¨???????¨????
            first = R[i][j:j+2]; second = R[i+1][j:j+2]

            # .#        ##
            # ## ????????? .# ?????????????????´????????????
            if (first == '.#' and second == '##') or (first == '##' and second == '.#'):
                k = j
                # #.        #.        ##
                # ## ????????? #. ????????? #. ?????°??????????????§???????????????
                while k+1 < w and R[i][k+1] != '.' and R[i+1][k+1] != '.':
                    k += 1
                if k+1 < w and ((R[i][k+1] == '#') ^ (R[i+1][k+1] == '#')):
                    # #.        ##
                    # ## ????????? #. ????????????????????§(i, j)??¨(i, k)?????????
                    P.append(((i, j), (i, k))) # (P)
                    conn[i][j] += 1
                    conn[i][k] += 1

            # .#        #.
            # ## ????????? ## ?????????????????´????????????
            if first in ['.#', '#.'] and second == '##':
                k = i
                # ##        ##        ##
                # #. ????????? .. ????????? .# ?????°??????????????§???????????????
                while k+1 < h and R[k+1][j] != '.' and R[k+1][j+1] != '.':
                    k += 1
                if k+1 < h and ((R[k+1][j] == '#') ^ (R[k+1][j+1] == '#')):
                    # ##        ##
                    # .# ????????? #. ????????????????????§(i, j)??¨(k, j)?????????
                    Q.append(((i, j), (k, j))) # (Q)
                    conn[i][j] += 1
                    conn[k][j] += 1

            if first.count('#') + second.count('#') == 3:
                dep += 1

    # ?????¨??°??????????§????
    dinic = Dinic(2 + len(P) + len(Q))
    # (s) -> (P)
    for i in xrange(len(P)):
        dinic.add_edge(0, i+2, 1)
    # (Q) -> (t)
    for i in xrange(len(Q)):
        dinic.add_edge(len(P)+i+2, 1, 1)
    # (P) -> (Q): ????????????????????????????£?????????§??????
    for i, p in enumerate(P):
        (a, b), (a, s) = p
        for j, q in enumerate(Q):
            (c, d), (t, d) = q

            # ((a, b), (a, s)) ??¨ ((c, d), (t, d)) ??????????????§??????
            if c <= a <= t and b <= d <= s:
                dinic.add_edge(i+2, len(P) + j+2, 1)

    # ???????????° = (???????§???° = ?????§???????????°) - (????????????????????¨?????§?????????????§???°)
    #
    # (????????????????????¨?????§?????????????????°) = (????????????????????????????????§??¬??????????????°)
    # => ?±??????£?????¬?????????{e1, e2}?????????????????????e1?????????e2?????????????????£????????????????????
    #    (?????????????????¨???????????????????????¢?????§????¨???????????????§???????????????????????)
    print dep - (len(P) + len(Q) - dinic.max_flow(0, 1)) + 1

Submission status: Accepted

Solution code:
# Dinic algorithm
from collections import deque
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

while 1:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break

    R = [raw_input() for i in xrange(h)]

    conn = [[0 for i in xrange(w)] for i in xrange(h)]

    P = []
    Q = []
    dep = 0

    for i in xrange(h-1):
        for j in xrange(w-1):
            first = R[i][j:j+2]; second = R[i+1][j:j+2]

            #                       .#    ##
            # if R[i:i+2][j:j+2] is ## or .#
            if (first == '.#' and second == '##') or (first == '##' and second == '.#'):
                k = j
                #                              #.     #.     ##
                # while R[i:i+2][k:k+2] is not ## and #. and #.
                while k+1 < w and R[i][k+1] != '.' and R[i+1][k+1] != '.':
                    k += 1
                #                       #.    ##
                # if R[i:i+2][k:k+2] is ## or #.
                if k+1 < w and ((R[i][k+1] == '#') ^ (R[i+1][k+1] == '#')):
                    P.append(((i, j), (i, k))) # (P)
                    conn[i][j] += 1
                    conn[i][k] += 1

            #                       .#    #.
            # if R[i:i+2][j:j+2] is ## or ##
            if first in ['.#', '#.'] and second == '##':
                k = i
                #                              ##     ##     ##
                # while R[k:k+2][j:j+2] is not #. and .. and .#
                while k+1 < h and R[k+1][j] != '.' and R[k+1][j+1] != '.':
                    k += 1
                #                       ##    ##
                # if R[k:k+2][j:j+2] is #. or .#
                if k+1 < h and ((R[k+1][j] == '#') ^ (R[k+1][j+1] == '#')):
                    Q.append(((i, j), (k, j))) # (Q)
                    conn[i][j] += 1
                    conn[k][j] += 1

            if first.count('#') + second.count('#') == 3:
                dep += 1

    # Bipartite graph
    dinic = Dinic(2 + len(P) + len(Q))
    # (s) -> (P)
    for i in xrange(len(P)):
        dinic.add_edge(0, i+2, 1)
    # (Q) -> (t)
    for i in xrange(len(Q)):
        dinic.add_edge(len(P)+i+2, 1, 1)
    # (P) -> (Q)
    for i, p in enumerate(P):
        (a, b), (a, s) = p
        for j, q in enumerate(Q):
            (c, d), (t, d) = q

            # check if two line segments intersect
            if c <= a <= t and b <= d <= s:
                dinic.add_edge(i+2, len(P) + j+2, 1)
    print dep - (len(P) + len(Q) - dinic.max_flow(0, 1)) + 1

Submission status: Accepted

Solution code:
# Dinic algorithm
from collections import deque
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

while 1:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break

    R = [raw_input() for i in xrange(h)]

    P = []; Q = []
    dep = 0

    for i in xrange(h-1):
        for j in xrange(w-1):
            first = R[i][j:j+2]; second = R[i+1][j:j+2]

            #                       .#    ##
            # if R[i:i+2][j:j+2] is ## or .#
            if (first == '.#' and second == '##') or (first == '##' and second == '.#'):
                k = j
                #                              #.     #.     ##
                # while R[i:i+2][k:k+2] is not ## and #. and #.
                while k+1 < w and R[i][k+1] != '.' and R[i+1][k+1] != '.':
                    k += 1
                #                       #.    ##
                # if R[i:i+2][k:k+2] is ## or #.
                if k+1 < w and ((R[i][k+1] == '#') ^ (R[i+1][k+1] == '#')):
                    P.append(((i, j), (i, k))) # (P)

            #                       .#    #.
            # if R[i:i+2][j:j+2] is ## or ##
            if first in ['.#', '#.'] and second == '##':
                k = i
                #                              ##     ##     ##
                # while R[k:k+2][j:j+2] is not #. and .. and .#
                while k+1 < h and R[k+1][j] != '.' and R[k+1][j+1] != '.':
                    k += 1
                #                       ##    ##
                # if R[k:k+2][j:j+2] is #. or .#
                if k+1 < h and ((R[k+1][j] == '#') ^ (R[k+1][j+1] == '#')):
                    Q.append(((i, j), (k, j))) # (Q)

            if first.count('#') + second.count('#') == 3:
                dep += 1

    # Bipartite graph
    dinic = Dinic(2 + len(P) + len(Q))
    # (s) -> (P)
    for i in xrange(len(P)):
        dinic.add_edge(0, i+2, 1)
    # (Q) -> (t)
    for i in xrange(len(Q)):
        dinic.add_edge(len(P)+i+2, 1, 1)
    # (P) -> (Q)
    for i, p in enumerate(P):
        (a, b), (a, s) = p
        for j, q in enumerate(Q):
            (c, d), (t, d) = q

            # check if two line segments intersect
            if c <= a <= t and b <= d <= s:
                dinic.add_edge(i+2, len(P) + j+2, 1)
    print dep - (len(P) + len(Q) - dinic.max_flow(0, 1)) + 1

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:
    """
    Dinicのアルゴリズム。最大流問題を解くことができます。
    https://tjkendev.github.io/procon-library/python/max_flow/dinic.html
    """

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def get_corner2corner_lines(B):
    H = len(B)
    W = len(B[0])
    vertical = []
    for i in range(H-1):
        for j in range(W-1):
            square = [B[i][j:j+2], B[i+1][j:j+2]]
            if square in [[".#", "##"], ["#.", "##"]]:
                tmp_i = i
                while tmp_i+1 < H and B[tmp_i+1][j:j+2] == "##":
                    tmp_i += 1
                if tmp_i+1 < H and B[tmp_i+1][j:j+2] in ["#.", ".#"]:
                    vertical.append((i, j, tmp_i))
    return vertical


def rotate(B):
    H = len(B)
    W = len(B[0])
    C = ["" for j in range(W)]
    for j in range(W):
        for i in range(H):
            C[j] += B[i][j]
    return C


def solve(B):
    H = len(B)
    W = len(B[0])

    horizontal = []
    vertical = []
    corners = 0
    for i in range(H-1):
        for j in range(W-1):
            square = [B[i][j:j+2], B[i+1][j:j+2]]
            if square[0].count("#")+square[1].count("#") == 3:
                corners += 1
    vertical = get_corner2corner_lines(B)
    horizontal = get_corner2corner_lines(rotate(B))

    H = len(horizontal)
    V = len(vertical)
    source = H+V
    sink = source+1
    n = H+V+2
    dinic = Dinic(n)
    for i in range(H):
        dinic.add_edge(source, i, 1)
    for i in range(V):
        dinic.add_edge(H+i, sink, 1)

    for i, (b, a, s) in enumerate(horizontal):
        for j, (c, d, t) in enumerate(vertical):
            if c <= a <= t and b <= d <= s:
                dinic.add_edge(i, H+j, 1)

    max_flow = dinic.flow(source, sink)
    ans = corners-(H+V-max_flow)+1
    return ans


def main():
    while True:
        H, W = map(int, input().split())
        if H == 0:
            break
        B = [input() for _ in range(H)]
        ans = solve(B)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# encoding: shift-jis

# Dinic algorithm
from collections import deque
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in xrange(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in xrange(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

while 1:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break

    R = [raw_input() for i in xrange(h)]

    conn = [[0 for i in xrange(w)] for i in xrange(h)]

    P = []
    Q = []
    dep = 0

    for i in xrange(h-1):
        for j in xrange(w-1):
            # ??£?????¨???????¨????
            first = R[i][j:j+2]; second = R[i+1][j:j+2]

            # .#        ##
            # ## ????????? .# ?????????????????´????????????
            if (first == '.#' and second == '##') or (first == '##' and second == '.#'):
                k = j
                # #.        #.        ##
                # ## ????????? #. ????????? #. ?????°??????????????§???????????????
                while k+1 < w and R[i][k+1] != '.' and R[i+1][k+1] != '.':
                    k += 1
                if k+1 < w and ((R[i][k+1] == '#') ^ (R[i+1][k+1] == '#')):
                    # #.        ##
                    # ## ????????? #. ????????????????????§(i, j)??¨(i, k)?????????
                    P.append(((i, j), (i, k))) # (P)
                    conn[i][j] += 1
                    conn[i][k] += 1

            # .#        #.
            # ## ????????? ## ?????????????????´????????????
            if first in ['.#', '#.'] and second == '##':
                k = i
                # ##        ##        ##
                # #. ????????? .. ????????? .# ?????°??????????????§???????????????
                while k+1 < h and R[k+1][j] != '.' and R[k+1][j+1] != '.':
                    k += 1
                if k+1 < h and ((R[k+1][j] == '#') ^ (R[k+1][j+1] == '#')):
                    # ##        ##
                    # .# ????????? #. ????????????????????§(i, j)??¨(k, j)?????????
                    Q.append(((i, j), (k, j))) # (Q)
                    conn[i][j] += 1
                    conn[k][j] += 1

            if first.count('#') + second.count('#') == 3:
                dep += 1

    # ?????¨??°??????????§????
    dinic = Dinic(2 + len(P) + len(Q))
    # (s) -> (P)
    for i in xrange(len(P)):
        dinic.add_edge(0, i+2, 1)
    # (Q) -> (t)
    for i in xrange(len(Q)):
        dinic.add_edge(len(P)+i+2, 1, 1)
    # (P) -> (Q): ????????????????????????????£?????????§??????
    for i, p in enumerate(P):
        (a, b), (a, s) = p
        for j, q in enumerate(Q):
            (c, d), (t, d) = q

            # ((a, b), (a, s)) ??¨ ((c, d), (t, d)) ??????????????§??????
            if c <= a <= t and b <= d <= s:
                dinic.add_edge(i+2, len(P) + j+2, 1)

    # ???????????° = (???????§???° = ?????§???????????°) - (????????????????????¨?????§?????????????§???°)
    #
    # (????????????????????¨?????§?????????????????°) = (????????????????????????????????§??¬??????????????°)
    # => ?±??????£?????¬?????????{e1, e2}?????????????????????e1?????????e2?????????????????£????????????????????
    #    (?????????????????¨???????????????????????¢?????§????¨???????????????§???????????????????????)
    print dep - (len(P) + len(Q) - dinic.max_flow(0, 1)) + 1