#P18164. Express Eviction

Express Eviction

Express Eviction

Bajtocja 是一块由 HH 行 WW 列格子组成的矩形土地。每个格子的边界都是一条交通稀少的道路。每个格子为空地,或住着一位居民。居民喜欢安静,不愿住在计划修建的快速路旁。

你要规划一条从矩形左上角到右下角的快速路。为了降低建设费用,路线只能沿已有道路行进。路线的长度和转弯次数不受限制。

凡是格子与快速路共边、甚至只碰到一个角,该格子里的居民都必须搬迁。同一居民无论被路线碰到多少次,都只算搬迁一人。

最少需要搬迁多少位居民?

输入格式

第一行两个整数 H,WH,W,满足 1≤H,W≤501\le H,W\le50。

接下来 HH 行,每行一个长度为 WW 的字符串,仅包含 . 和 #。. 表示空地,# 表示该格子住着一位居民。

输出格式

输出一个整数,表示最少需要搬迁的居民数。

样例

输入:

4 6
.##...
.#....
##....
....#.

输出:

1

搬迁第 3 行第 1 列的居民后即可修路。例如把道路交点用从 0 开始的 (行,列) 表示,可沿 (0,0)→(4,0)→(4,3)→(2,3)→(2,6)→(4,6) 行进,每段都沿现有道路。路线允许向上或向左折返,不要求单调。

原题样例路线:叉号表示搬迁的居民,粗线表示快速路