Problem:
 Score : 150 points    Problem Statement  There are some goats on a grid with H rows and W columns. 
  Alice wants to put some fences at some cells where goats do not exist so that no goat can get outside the grid. 
  Goats can move in the four directions, that is, up, down, right and left.
  Goats can not move onto the cells where fences are placed. 
  If a goat exists at one of the outermost cells in the grid, it can move outside.
  Goats do not move until all fences are placed.  
  Find the minimum number of fences to be placed.      Constraints    1 \leq H \leq 100    1 \leq W \leq 100   There is at least one goat on the given grid.         Input  The input is given from the Standart Input in the following format:   H  W  S_1 : S_H   The j -th (1 \leq j \leq W) character in S_i  (1 \leq i \leq H) represents 
  whether a goat exists at the cell located at row i and column j . 
  Character . represents there is no goat, and X represents there is one goat at the cell.

Solution (Python):
from collections import deque


class Dinic:
    def __init__(self, N, inf):
        self.N = N
        self.inf = inf
        self.G = [[] for _ in range(N)]
        self.level = [0]*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):
        self.level = [-1]*self.N
        deq = deque([s])
        self.level[s] = 0
        while deq:
            v = deq.pop()
            lv = self.level[v] + 1
            for w, cap, _ in self.G[v]:
                if cap > 0 and self.level[w] == -1:
                    self.level[w] = lv
                    deq.appendleft(w)

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

    def flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] == -1:
                return flow
            *self.iter, = map(iter, self.G)
            f = self.inf
            while f > 0:
                f = self.dfs(s, t, self.inf)
                flow += f


import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())  


H,W = MI()
S = [LS2() for _ in range(H)]

Di = Dinic(2*H*W+2,10000)
s,t = 2*H*W,2*H*W+1

for i in range(H):
    for j in range(W):
        if S[i][j] == 'X':
            Di.add_edge(s,W*i+j,10000)

for j in range(W):
    Di.add_edge(H*W+j,t,10000)
    Di.add_edge(H*W+W*(H-1)+j,t,10000)
for i in range(1,H-1):
    Di.add_edge(H*W+W*i,t,10000)
    Di.add_edge(H*W+W*i+(W-1),t,10000)

for i in range(H):
    for j in range(W-1):
        Di.add_edge(H*W+W*i+j,W*i+(j+1),10000)
        Di.add_edge(H*W+W*i+(j+1),W*i+j,10000)
for i in range(H-1):
    for j in range(W):
        Di.add_edge(H*W+W*i+j,W*(i+1)+j,10000)
        Di.add_edge(H*W+W*(i+1)+j,W*i+j,10000)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            Di.add_edge(W*i+j,H*W+W*i+j,1)
        else:
            Di.add_edge(W*i+j,H*W+W*i+j,10000)

flow = Di.flow(s,t)
print(flow if flow < 10000 else -1)

Solution (Python):
import sys
import itertools
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import maximum_flow

H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = source * 2

graph = lil_matrix((sink + 1, sink + 1), dtype=int)

for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        graph[2 * i, 2 * i + 1] = 1
    else:
        graph[source, 2 * i + 1] = INF
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            graph[2 * i + 1, 2 * j] = 1
        else:
            graph[2 * i + 1, sink] = INF
graph = graph.tocsr()
ans = maximum_flow(graph, source, sink).flow_value
ans = ans if ans < INF else -1
print(ans)

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

"""
・最小カット
・頂点でカットする場合には、v_in, v_outに分ける
・v_in, v_outの間に容量1の辺
・sourceから、ヤギ_outに容量無限大の辺
・外周_outから、sinkに容量無限大の辺
"""
H,W = map(int,readline().split())
S = b''.join(read().split())

class Dinic:
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink

    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) 

    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1])

    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level

    def dfs(self):
        INF = 10**18
        G = self.G
        sink = self.sink
        prog = self.progress
        level = self.level
        ascend = False
        ff = 0
        stack = [(self.source,INF)]
        while stack:
            if ff:
                
                v,f = stack.pop()
                p = prog[v]
                to, cap, rev = G[v][p]
                G[v][p][1] -= ff
                G[to][rev][1] += ff
                continue
            v,f = stack[-1]
            if v == sink:
                ff = f
                stack.pop()
                continue
            E = G[v]
            lv = level[v]
            if ascend:
                
                prog[v] += 1
            find_flag = False
            for i in range(prog[v],len(E)):
                to, cap, rev = E[i]
                prog[v] = i
                if not cap:
                    continue
                if level[to] <= lv:
                    continue
                find_flag = True
                break
            if not find_flag:
                ascend = True
                stack.pop()
                continue
            ascend = False
            x = f if f < cap else cap
            stack.append((to,x))
        return ff

    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs()
                if not f:
                    break
                flow += f
        return flow



source = 2*H*W
sink = source+1

INF = 10**12

dinic = Dinic(2*H*W+2,source,sink)
add = dinic.add_edge
for i in range(H*W):
    h,w = divmod(i,W)
    if S[i] == ord('.'):
        add(i+i,i+i+1,1)
    else:
        add(i+i,sink,INF)
        
    for dh,dw in ((1,0),(-1,0),(0,1),(0,-1)):
        h1 = h + dh; w1 = w + dw
        if 0 <= h1 < H and 0 <= w1 < W:
            j = h1 * W + w1
            add(i+i+1,j+j,1)
        else:
            
            add(source,i+i,INF)
            

dinic.source

f = dinic.max_flow()
answer = f if f < INF else -1
print(answer)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self, v, inf =10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v  
        self.ite = [0]*v  
    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 bfs(self, s):  
        self.level = [-1]*self.v  
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0: 
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])
    def dfs(self, v, t, f):  
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[v] = i
            e = self.G[v][i]
            if e[1]>0 and self.level[v]<self.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  
                    return d
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0:
                return flow
            self.ite = [0]*self.v  
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)

H, W = MAP()
S = [input() for _ in range(H)]

D = Dinic(2*H*W+2)
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
s = 2*H*W
t = 2*H*W+1
for i in range(H):
    for j in range(W):
        if S[i][j] == "X":
            if i == 0 or i == H-1  or j == 0 or j == W-1:
                print(-1)
                exit()
            D.add_edge(s, W*i+j, INF)
            for k in range(4):
                ny = i+dy[k]
                nx = j+dx[k]
                D.add_edge(W*i+j, W*ny+nx, INF)
        else:
            D.add_edge(W*i+j, W*H+W*i+j, 1)
            if i == 0 or i == H-1  or j == 0 or j == W-1:
                D.add_edge(H*W+W*i+j, t, INF)
            else:
                for k in range(4):
                    ny = i+dy[k]
                    nx = j+dx[k]
                    D.add_edge(H*W+W*i+j, W*ny+nx, INF)

print(D.max_flow(s, t))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class Dinic:
    """ 最大流(Dinic) """

    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        from collections import deque

        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, INF)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, INF)

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
HW = H * W
grid = build_grid(H, W, '', str, space=0)


dn = Dinic(2*H*W+2)
s = 2 * H * W
t = 2 * H * W + 1

for i in range(H):
    for j in range(W):
        
        if i != 0:
            dn.add_link(HW+i*W+j, i*W+j-W, INF)
        if i != H-1:
            dn.add_link(HW+i*W+j, i*W+j+W, INF)
        if j != 0:
            dn.add_link(HW+i*W+j, i*W+j-1, INF)
        if j != W-1:
            dn.add_link(HW+i*W+j, i*W+j+1, INF)
        
        if grid[i][j] == 'X':
            
            dn.add_link(s, i*W+j, INF)
            
            dn.add_link(i*W+j, HW+i*W+j, INF)
        else:
            
            dn.add_link(i*W+j, HW+i*W+j, 1)
        
        if i == 0 or i == H-1 or j == 0 or j == W-1:
            dn.add_link(HW+i*W+j, t, INF)

ans = dn.max_flow(s, t)
if ans >= INF:
    print(-1)
else:
    print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class Dinic:
    """ 最大流(Dinic) """

    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None
 
    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])
 
    def bfs(self, s):
        from collections import deque

        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth
 
    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0
 
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, INF)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, INF)

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
HW = H * W
grid = build_grid(H, W, '', str, space=0)


dn = Dinic(2*H*W+2)
s = 2 * H * W
t = 2 * H * W + 1

for i in range(H):
    for j in range(W):
        
        if i != 0:
            dn.add_link(HW+i*W+j, i*W+j-W, INF)
        if i != H-1:
            dn.add_link(HW+i*W+j, i*W+j+W, INF)
        if j != 0:
            dn.add_link(HW+i*W+j, i*W+j-1, INF)
        if j != W-1:
            dn.add_link(HW+i*W+j, i*W+j+1, INF)
        
        if grid[i][j] == 'X':
            
            dn.add_link(s, i*W+j, INF)
            
            dn.add_link(i*W+j, HW+i*W+j, INF)
        else:
            
            dn.add_link(i*W+j, HW+i*W+j, 1)
        
        if i == 0 or i == H-1 or j == 0 or j == W-1:
            dn.add_link(HW+i*W+j, t, INF)

ans = dn.max_flow(s, t)
if ans >= INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

"""
・最小カット
・頂点でカットする場合には、v_in, v_outに分ける
・v_in, v_outの間に容量1の辺
・sourceから、ヤギ_outに容量無限大の辺
・外周_outから、sinkに容量無限大の辺
"""

H,W = map(int,readline().split())
S = b''.join(read().split())

class Dinic:
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink

    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) 
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1])
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self):
        INF = 10**18
        G = self.G
        sink = self.sink
        prog = self.progress
        level = self.level
        ascend = False
        ff = 0
        stack = [(self.source,INF)]
        while stack:
            if ff:
                
                v,f = stack.pop()
                p = prog[v]
                to, cap, rev = G[v][p]
                G[v][p][1] -= ff
                G[to][rev][1] += ff
                continue
            v,f = stack[-1]
            if v == sink:
                ff = f
                stack.pop()
                continue
            E = G[v]
            lv = level[v]
            if ascend:
                
                prog[v] += 1
            find_flag = False
            for i in range(prog[v],len(E)):
                to, cap, rev = E[i]
                prog[v] = i
                if not cap:
                    continue
                if level[to] <= lv:
                    continue
                find_flag = True
                break
            if not find_flag:
                ascend = True
                stack.pop()
                continue
            ascend = False
            x = f if f < cap else cap
            stack.append((to,x))
        return ff
    
    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs()
                if not f:
                    break
                flow += f
        return flow



source = 2*H*W
sink = source+1

INF = 10**12

dinic = Dinic(2*H*W+2,source,sink)
add = dinic.add_edge
for i in range(H*W):
    h,w = divmod(i,W)
    if S[i] == ord('.'):
        add(i+i,i+i+1,1)
    else:
        add(source,i+i+1,INF)
    for dh,dw in ((1,0),(-1,0),(0,1),(0,-1)):
        h1 = h + dh; w1 = w + dw
        if 0 <= h1 < H and 0 <= w1 < W:
            j = h1 * W + w1
            add(i+i+1,j+j,1)
        else:
            
            add(i+i+1,sink,INF)

dinic.source

f = dinic.max_flow()
answer = f if f < INF else -1
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

"""
・最小カット
・頂点でカットする場合には、v_in, v_outに分ける
・v_in, v_outの間に容量1の辺
・sourceから、ヤギ_outに容量無限大の辺
・外周_outから、sinkに容量無限大の辺
"""

H,W = map(int,readline().split())
S = b''.join(read().split())

class Dinic:
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink

    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) 
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1])
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self):
        INF = 10**18
        G = self.G
        sink = self.sink
        prog = self.progress
        level = self.level
        ascend = False
        ff = 0
        stack = [(self.source,INF)]
        while stack:
            if ff:
                
                v,f = stack.pop()
                p = prog[v]
                to, cap, rev = G[v][p]
                G[v][p][1] -= ff
                G[to][rev][1] += ff
                continue
            v,f = stack[-1]
            if v == sink:
                ff = f
                stack.pop()
                continue
            E = G[v]
            lv = level[v]
            if ascend:
                
                prog[v] += 1
            find_flag = False
            for i in range(prog[v],len(E)):
                to, cap, rev = E[i]
                prog[v] = i
                if not cap:
                    continue
                if level[to] <= lv:
                    continue
                find_flag = True
                break
            if not find_flag:
                ascend = True
                stack.pop()
                continue
            ascend = False
            x = f if f < cap else cap
            stack.append((to,x))
        return ff
    
    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs()
                if not f:
                    break
                flow += f
        return flow



source = 2*H*W
sink = source+1

INF = 10**12

dinic = Dinic(2*H*W+2,source,sink)
add = dinic.add_edge
for i in range(H*W):
    h,w = divmod(i,W)
    if S[i] == ord('.'):
        add(i+i,i+i+1,1)
    else:
        add(source,i+i+1,INF)
    for dh,dw in ((1,0),(-1,0),(0,1),(0,-1)):
        h1 = h + dh; w1 = w + dw
        if 0 <= h1 < H and 0 <= w1 < W:
            j = h1 * W + w1
            add(i+i+1,j+j,1)
        else:
            
            add(i+i+1,sink,INF)

dinic.source

f = dinic.max_flow()
answer = f if f < INF else -1
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

"""
・最小カット
・頂点でカットする場合には、v_in, v_outに分ける
・v_in, v_outの間に容量1の辺
・sourceから、ヤギ_outに容量無限大の辺
・外周_outから、sinkに容量無限大の辺
"""

class Dinic:
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink

    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) 
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1])
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        G = self.G
        prog = self.progress
        level = self.level
        lv = level[v]
        E = G[v]
        for i in range(prog[v],len(E)):
            to, cap, rev = E[i]
            prog[v] = i
            if not cap:
                continue
            if level[to] <= lv:
                continue
            x = f if f < cap else cap
            ff = self.dfs(to, x)
            if ff:
                E[i][1] -= ff
                G[to][rev][1] += ff
                return ff
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs(self.source, INF)
                if not f:
                    break
                flow += f
        return flow

H,W = map(int,readline().split())
S = b''.join(read().split())



source = 2*H*W
sink = source+1

INF = 10**12

dinic = Dinic(2*H*W+2,source,sink)
add = dinic.add_edge
for i in range(H*W):
    h,w = divmod(i,W)
    if S[i] == ord('.'):
        add(i+i,i+i+1,1)
    else:
        add(source,i+i+1,INF)
    for dh,dw in ((1,0),(-1,0),(0,1),(0,-1)):
        h1 = h + dh; w1 = w + dw
        if 0 <= h1 < H and 0 <= w1 < W:
            j = h1 * W + w1
            add(i+i+1,j+j,1)
        else:
            
            add(i+i+1,sink,INF)

f = dinic.max_flow()
answer = f if f < INF else -1
print(answer)