拦截蚁群

Zero的节点分裂了——像细胞分裂一样，传感器节点在左，处理器节点在右。它们之间由无数条发光的链路连接，每一条链路都在嗡嗡作响，像无数只蚂蚁在搬运食物。

"蚁群。"Echo说，"Zero的底层通信协议。信息像蚂蚁一样，从左边的传感器爬到右边的处理器。"

"我们要做啥子？"CC问。

"在网格上放障碍物。"你说，"阻止蚁群从左岸走到右岸。"

"这就像……"CC想了想，"像防火带。在林子中间挖一条沟，让火烧不过来。"

"对。"

你开始写。网格是一个棋盘，有些格子是空地，有些是障碍。蚁群可以从左岸的任意格子出发，走到右岸的任意格子——只能上下左右走空地。我们要在空地上放置尽可能多的障碍物，使得蚁群无法从左岸到达右岸。

屏幕上跳出了结果。最多放置：47个障碍。

"又是47。"CC说。

"47个障碍。"Echo说，"挡住47条蚁路。"

"能挡住全部？"你问。

"能。"Echo说，"但代价是——47个格子永远不能再走。"

"值得的。"CC说，"只要人能活。"

题目描述

$n\times m$ 的网格。有些格子是空地 .，有些是障碍 #。可以在空地上放置障碍（每个空地最多放一次）。求最多能放置多少个障碍，使得不存在从左边界到右边界的通路（只能上下左右走空地）。

输入格式

$n, m$。然后 $n$ 行字符串表示网格。

输出格式

最多放置的障碍数。

输入样例

3 2
1 2
2 3

输出样例

2
1
3

提示

• 二分图最小割。把网格按坐标和的奇偶性染成二分图。
• 左边界点为源点，右边界点为汇点，求最小割。
• 最小割 = 最大流，用Dinic算法。

"蚁群挡住了。"你说。

"47个。"Echo说，"47条命。"

"不是47条命。"CC说，"是47个选择。"

"选择？"

"对。"CC说，"选择让谁活。"

Echo没有说话。但她的服务器指示灯变成了红色——不是危险，是像火焰一样的、燃烧的红。

"下一题。"她说，"是战车。"

[第二题：布设战车]