【問題】H 行 W 列のグリッド状のフィールドに羊が何頭かいる。羊たちは最初フィールドのいずれかのマス上におり、上下左右隣り合うマスに移動できる。あなたはフィールドのマス上に柵を建てることができる。羊がフィールドの外に脱出できないようにするには最低何個の柵を建てればよいか。

【制約】1 <= H <= 100, 1 <= W <= 100

グラフの最小点カットを最小(辺)カットに帰着する方法を体得した。

【問題】Gをグラフ、s, t をその相異なる頂点とする。G の(s, t 以外の)頂点をいくつか除去することによって頂点 s から頂点 t へ至るパスが存在しないようにしたい。頂点 i の除去コストは c[i] である。目的を達成するため必要な最小コストはいくらか。

これを最小(辺)カットに帰着する。新しいグラフG_newを作る。G_newの頂点は x_in, x_out (x は Gの頂点)である。 x_in -> x_out にキャパシティ c[x]の辺を張る。ただし s_in -> s_out, t_in -> t_out はキャパシティ∞とする。また x -> y が G の辺であるとき、x_out -> y_in にキャパシティ∞の辺を張る。

以上により新しく構成されたグラフG_new上でs_in -> t_outの最小カットを解けば元の問題が解ける。

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque

class Edge():
   def __init__(self, to, cap, rev):
       self.to = to
       self.cap = cap
       self.rev = rev

class Dinic():
   def __init__(self, N, inf = float('inf')):
       self.N = N
       self.G = [[] for _ in range(N)]
       self.level = [-1]*N
       self.it = [0]*N
       self.inf = inf

   def add_edge(self, fr, to, cap):
       self.G[fr].append(Edge(to, cap, len(self.G[to])))
       self.G[to].append(Edge(fr, 0, len(self.G[fr]) - 1))

   def bfs(self, s):
       self.level = [-1]*self.N
       self.level[s] = 0
       q = deque([s])
       while q:
           v = q.popleft()
           for i in range(len(self.G[v])):
               e = self.G[v][i]
               if e.cap > 0 and self.level[e.to] < 0:
                   self.level[e.to] = self.level[v] + 1
                   q.append(e.to)

   def dfs(self, v, t, f):
       if v == t:
           return f
       for i in range(self.it[v], len(self.G[v])):
           self.it[v] = i
           e = self.G[v][i]
           if e.cap > 0 and self.level[v] < self.level[e.to]:
               d = self.dfs(e.to, t, min(f, e.cap))
               if d > 0:
                   e.cap -= d
                   self.G[e.to][e.rev].cap += 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.it = [0]*self.N
           f = self.dfs(s, t, self.inf)
           while f > 0:
               flow += f
               f = self.dfs(s, t, self.inf)


def main():
   INF = float('inf')

   H, W = map(int, readline().split())
   S = [readline().strip() for _ in range(H)]
   source = 2 * H * W
   sink = 2 * H * W + 1
   dinic = Dinic(2 * H * W + 2, INF)
   add = dinic.add_edge
   for i in range(H):
       for j in range(W):
           p_in = i * W + j
           p_out = p_in + H * W
           if S[i][j] == '.':
               add(p_in, p_out, 1)
           else:
               add(source, p_out, INF)
           if i == 0 or i == H - 1 or j == 0 or j == W - 1:
               add(p_out, sink, INF)
           else:
               for delta in (1, -1, W, -W):
                   add(p_out, p_in + delta, INF)
   f = dinic.max_flow(source, sink)
   print(f if f < INF else -1)
     
if __name__ == '__main__':
   main()