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):
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)

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

from collections import defaultdict

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

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

INF = 10**12

source = -1
sink = -2
graph = defaultdict(dict)
for i in range(H*W):
    h,w = divmod(i,W)
    if S[i] == ord('.'):
        graph[i+i][i+i+1] = 1
        graph[i+i+1][i+i] = 0
    else:
        graph[source][i+i+1] = INF
        graph[i+i+1][source] = 0
    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
            graph[i+i+1][j+j] = 1
            graph[j+j][i+i+1] = 0
        else:
            
            graph[i+i+1][sink] = INF
            graph[sink][i+i+1] = 0

class Dinic():
    def __init__(self,graph,V,source,sink):
        self.graph = graph
        self.sink = sink
        self.source = source
        self.V = V
        self.compress()
        
    def compress(self):
        self.N = len(self.V)
        v_to_i = {x:i for i,x in enumerate(self.V)}
        self.sink = v_to_i[self.sink]
        self.source = v_to_i[self.source]
        g = [dict() for _ in range(self.N)]
        for v,e in self.graph.items():
            vn = v_to_i[v]
            g[vn] = {v_to_i[w]:c for w,c in e.items()}
        self.graph = g
        
    def bfs(self):
        level = [0]*self.N
        q = [self.source]
        level[self.source] = 1
        d = 1
        while q:
            if level[self.sink]:
                break
            qq = []
            d += 1
            for v in q:
                for w,cap in self.graph[v].items():
                    if cap == 0:
                        continue
                    if level[w]:
                        continue
                    level[w] = d
                    qq.append(w)
            q = qq
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        for w,cap in self.itr[v]:
            if cap == 0 or self.level[w] != self.level[v] + 1:
                continue
            d = self.dfs(w,min(f,cap))
            if d:
                self.graph[v][w] -= d
                self.graph[w][v] += d
                return d
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.itr = [iter(e.items()) for e in self.graph]
            while True:
                f = self.dfs(self.source,INF)
                if f == 0:
                    break
                flow += f
        return flow

f = Dinic(graph,set(graph),source,sink).max_flow()

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

Solution (Python):

import collections
import queue


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u]) - 1])
            self.edges[v].append([u, c, len(self.edges[u])])
            self.edges[u].append([v, 0, len(self.edges[v]) - 1])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = collections.deque([s]) 
        
        while que: 
            v = que.popleft() 
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0]) 

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[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.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


H, W = map(int, input().split())
graph = Dinic(2*H*W + 2)
delta = [-1, 1, W, -W]
goal = 2 * H * W + 1
for i in range(H):
    S = str(input())
    for j, s in enumerate(S):
        curEdge = i * W + j + 1
        if s == '.':
            graph.add(curEdge, curEdge+H*W, 1)
        else:
            if i == 0 or i == H-1 or j == 0 or j == W-1:
                print(-1)
                quit()
            graph.add(curEdge, curEdge+H*W, float('inf'))
            graph.add(0, curEdge, float('inf'))
        for d in delta:
            if 0 < curEdge+d < 2*H*W+1:
                graph.add(curEdge+H*W, curEdge+d, float('inf'))

for i in range(1, W+1):
    graph.add(i+H*W, goal, float('inf'))
    graph.add(i+(2*H-1)*W, goal, float('inf'))

for i in range(1, H-1):
    graph.add((i+H)*W+1, goal, float('inf'))
    graph.add((i+H+1)*W, goal, float('inf'))


print(graph.maxFlow(0, goal))

Solution (Python):
import itertools
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
S = [sys.stdin.readline().rstrip() for _ in range(H)]


class Dinic:
    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int)) graph: (to, cap) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap in graph[v]:
                rev = [v, 0]
                edge = [u, cap, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def _dist(self, s):
        """
        :param int s:
        :rtype: list of int
        :return: s からの距離。残余グラフ上で到達できない場合は -1
        """
        ret = [-1] * len(self.graph)
        ret[s] = 0
        que = deque([(s, 0)])
        while que:
            v, d = que.popleft()
            for u, cap, _ in self.graph[v]:
                if ret[u] < 0 < cap:
                    ret[u] = d + 1
                    que.append((u, d + 1))
        return ret

    def _dfs(self, s, t, dist, iter, flow=float('inf')):
        """
        :param int s:
        :param int t:
        :param list of int dist:
        :param list of int iter:
        :param int flow:
        """
        if s == t:
            return flow
        while iter[s] < len(self.graph[s]):
            edge = self.graph[s][iter[s]]
            to, cap, rev = edge
            if dist[s] < dist[to] and cap > 0:
                f = self._dfs(to, t, dist, iter, min(flow, cap))
                if f > 0:
                    edge[1] -= f
                    rev[1] += f
                    return f
            iter[s] += 1
        return 0

    def maximum_flow(self, from_v, to_v):
        """
        :param int from_v:
        :param int to_v:
        :return: from_v から to_v への最大流
        """
        ret = 0
        while True:
            dist = self._dist(from_v)
            if dist[to_v] < 0:
                break
            iter = [0] * len(self.graph)
            while True:
                flow = self._dfs(from_v, to_v, dist, iter)
                if flow == 0:
                    break
                ret += flow
        return ret


graph = [[] for _ in range(H * W * 2 + 2)]
st = H * W * 2
en = H * W * 2 + 1
offset = H * W
for h, w in itertools.product(range(H), range(W)):
    pin = h * W + w
    pout = pin + offset
    if S[h][w] == "X":
        graph[st].append((pout, IINF))
    else:
        graph[pin].append((pout, 1))
    for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        h2, w2 = h + dh, w + dw
        if 0 <= h2 < H and 0 <= w2 < W:
            qin = h2 * W + w2
            graph[pout].append((qin, IINF))
        else:
            graph[pout].append((en, IINF))

mincut = Dinic(graph=graph).maximum_flow(st, en)
if mincut >= IINF:
    print(-1)
else:
    print(mincut)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque

class Dinic:
    def __init__(self,n,edges):
        self.n=n
        self.edges=[[] for _ in range(n)]
        self.iter=[0]*n
        self.level=None
        self.graph(edges)
    def graph(self,E):
        edges=self.edges
        for fr,to,cap in E:
            edges[fr].append([to,cap,len(edges[to])])
            edges[to].append([fr,0,len(edges[fr])-1])
    def maxflow(self,source,sink):
        max_flow=0
        while True:
            self.bfs(source)
            if self.level[sink]<0:
                return max_flow
            self.iter=[0]*self.n
            flow=self.dfs(source,sink,float('inf'))
            while flow:
                max_flow+=flow
                flow=self.dfs(source,sink,float('inf'))
    def bfs(self,source):
        edges=self.edges
        level=[-1]*self.n
        level[source]=0
        q=deque([source])
        while q:
            fr=q.popleft()
            for to,cap,_ in edges[fr]:
                if cap>0>level[to]:
                    level[to]=level[fr]+1
                    q.append(to)
        self.level=level
    def dfs(self,source,sink,flow):
        if source==sink:
            return flow
        while self.iter[source]<len(self.edges[source]):
            to,cap,rev=self.edges[source][self.iter[source]]
            if cap>0 and self.level[source]<self.level[to]:
                f=self.dfs(to,sink,min(flow,cap))
                if f:
                    self.edges[source][self.iter[source]][1]-=f
                    self.edges[to][rev][1]+=f
                    return f
            self.iter[source]+=1
        return 0

inf=float('inf')
h,w=map(int,input().split())
Edges=[]
delta=(-1,1,-w,w)
for i in range(h):
    S=tuple(input().strip())
    for j,s in enumerate(S):
        v=i*w+j+1
        if s=='.':
            Edges.append((v,v+h*w,1))
        else:
            Edges.append((v,v+h*w,inf))
            Edges.append((0,v,inf))
        for d in delta:
            if v+d<=0 or v+d>=2*h*w+1:
                continue
            Edges.append((v+h*w,v+d,inf))
for i in range(1,w+1):
    Edges.append((i+h*w,2*h*w+1,inf))
    Edges.append((i+(2*h-1)*w,2*h*w+1,inf))
for i in range(1,h-1):
    Edges.append(((i+h)*w+1,2*h*w+1,inf))
    Edges.append(((i+h+1)*w,2*h*w+1,inf))

dinic=Dinic(2*h*w+2,Edges)
mf=dinic.maxflow(0,2*h*w+1)
print(-1 if mf==inf else mf)

Solution (Python):
H, W = map(int, raw_input().split())
S_list = list()
for i in range(H):
    S_list.append(raw_input())


large_const = 100000










G = dict()
def add_node(s, Graph=G):
    Graph[s] = {'edges':dict()}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight

def max_flow_dinic(s, t, Graph=G):
    G_ = Graph
    max_flow = 0
    while True:
        
        
        for v in G_.keys():
            G_[v]['dist'] = -1
        
        G_[t]['dist'] = 0
        
        que_bfs = [t]
        dmax = large_const
        while len(que_bfs) > 0:
            v = que_bfs.pop(0)
            if G_[v]['dist'] >= dmax:
                
                pass
            else:
                
                for d in G_[v]['edges'].keys():    
                    if G_[d]['edges'][v] > 0:
                        if d == s:
                            
                            
                            dmax = min(dmax, G_[v]['dist'] + 1)
                            G_[d]['dist'] = dmax
                        elif G_[d]['dist'] == -1:
                            
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        elif G_[d]['dist'] > G_[v]['dist'] + 1:
                            
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        else:
                            pass
        
        if G_[s]['dist'] == -1:
            break
        else:
            
            
            que_dfs = [[s]]
            while len(que_dfs) > 0:
                path = que_dfs.pop()
                
                if len(path) == 1:
                    pass
                elif G_[path[0]]['edges'][path[1]] == 0:
                    continue
                v = path[-1]
                
                for d in G_[v]['edges'].keys():
                    if G_[v]['edges'][d] > 0 and G_[d]['dist'] == G_[v]['dist'] - 1:
                        if d == t:
                            
                            path.append(d)
                            
                            
                            eps = 1
                            max_flow += eps
                            
                            for i in range(len(path) - 1):
                                G_[path[i]]['edges'][path[i+1]] -= eps
                                G_[path[i+1]]['edges'][path[i]] += eps
                                
                                
                        else:
                            
                            que_dfs.append(path + [d])
            
    
    return max_flow




add_node('src')
add_node('dst')



for i in range(H):
    for j in range(W):
        if S_list[i][j] == 'X':
            pass
        else:
            add_node(str([i, j]) + '-src')
            add_node(str([i, j]) + '-dst')


for i in range(H):
    for j in range(W):
        if S_list[i][j] == 'X':
            pass
        else:
            add_edge(str([i, j]) + '-dst', str([i, j]) + '-src', 1)
            add_edge(str([i, j]) + '-src', str([i, j]) + '-dst', 0)
            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                k = i + d[0]
                l = j + d[1]
                if k in [-1, H] or l in [-1, W]:
                    add_edge('src', str([i, j]) + '-dst', 1)
                    add_edge(str([i, j]) + '-dst', 'src', 0)
                elif S_list[k][l] == 'X':
                    add_edge(str([i, j]) + '-src', 'dst', 1)
                    add_edge('dst', str([i, j]) + '-src', 0)                    
                else:
                    add_edge(str([i, j]) + '-src', str([k, l]) + '-dst', 1)
                    add_edge(str([k, l]) + '-dst', str([i, j]) + '-src', 0)

res = 0

if 'X' in S_list[0] or 'X' in S_list[H-1]:
    res = -1
elif 'X' in [s[0] for s in S_list] or 'X' in [s[W-1] for s in S_list]:
    res = -1
else:
    res = max_flow_dinic('src', 'dst')


print res

Solution (Python):
import numpy as np

H, W = map(int, raw_input().split())
S_list = list()
for i in range(H):
    S_list.append(raw_input())


large_const = 100000

X_mat = np.zeros((H, W), dtype='int')



for h in range(H):
    for w in range(W):
        if S_list[h][w] == 'X':
            X_mat[h, w] += 1


G = dict()
def add_node(s, Graph=G):
    Graph[s] = {'edges':dict()}
    
def add_edge(s, t, weight=1, Graph=G):
    Graph[s]['edges'][t] = weight

def max_flow_dinic(s, t, Graph=G):
    G_ = Graph
    max_flow = 0
    while True:
        
        
        for v in G_.keys():
            G_[v]['dist'] = -1
        
        G_[t]['dist'] = 0
        
        que_bfs = [t]
        dmax = large_const
        while len(que_bfs) > 0:
            v = que_bfs.pop(0)
            if G_[v]['dist'] >= dmax:
                
                pass
            else:
                
                for d in G_[v]['edges'].keys():    
                    if G_[d]['edges'][v] > 0:
                        if d == s:
                            
                            
                            dmax = min(dmax, G_[v]['dist'] + 1)
                            G_[d]['dist'] = dmax
                        elif G_[d]['dist'] == -1:
                            
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        elif G_[d]['dist'] > G_[v]['dist'] + 1:
                            
                            G_[d]['dist'] = G_[v]['dist'] + 1
                            que_bfs.append(d)
                        else:
                            pass
        
        if G_[s]['dist'] == -1:
            break
        else:
            
            
            que_dfs = [[s]]
            while len(que_dfs) > 0:
                path = que_dfs.pop()
                
                if len(path) == 1:
                    pass
                elif G_[path[0]]['edges'][path[1]] == 0:
                    continue
                v = path[-1]
                
                for d in G_[v]['edges'].keys():
                    if G_[v]['edges'][d] > 0 and G_[d]['dist'] == G_[v]['dist'] - 1:
                        if d == t:
                            
                            path.append(d)
                            
                            
                            eps = 1
                            max_flow += eps
                            
                            for i in range(len(path) - 1):
                                G_[path[i]]['edges'][path[i+1]] -= eps
                                G_[path[i+1]]['edges'][path[i]] += eps
                                
                                
                        else:
                            
                            que_dfs.append(path + [d])
            
    
    return max_flow




add_node('src')
add_node('dst')



for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_node(str([i, j]) + '-src')
            add_node(str([i, j]) + '-dst')


for i in range(H):
    for j in range(W):
        if X_mat[i, j] == 1:
            pass
        else:
            add_edge(str([i, j]) + '-dst', str([i, j]) + '-src', 1)
            add_edge(str([i, j]) + '-src', str([i, j]) + '-dst', 0)
            for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                k = i + d[0]
                l = j + d[1]
                if k in [-1, H] or l in [-1, W]:
                    add_edge('src', str([i, j]) + '-dst', 1)
                    add_edge(str([i, j]) + '-dst', 'src', 0)
                elif X_mat[k, l] == 1:
                    add_edge(str([i, j]) + '-src', 'dst', 1)
                    add_edge('dst', str([i, j]) + '-src', 0)                    
                else:
                    add_edge(str([i, j]) + '-src', str([k, l]) + '-dst', 1)
                    add_edge(str([k, l]) + '-dst', str([i, j]) + '-src', 0)

res = 0

if X_mat[0,:].sum() + X_mat[H-1,:].sum() + X_mat[:,0].sum() + X_mat[:,W-1].sum() > 0:
    res = -1
else:
    res = max_flow_dinic('src', 'dst')


print res