#P18164. Express Eviction
Express Eviction
Express Eviction
Bajtocja 是一块由 行 列格子组成的矩形土地。每个格子的边界都是一条交通稀少的道路。每个格子为空地,或住着一位居民。居民喜欢安静,不愿住在计划修建的快速路旁。
你要规划一条从矩形左上角到右下角的快速路。为了降低建设费用,路线只能沿已有道路行进。路线的长度和转弯次数不受限制。
凡是格子与快速路共边、甚至只碰到一个角,该格子里的居民都必须搬迁。同一居民无论被路线碰到多少次,都只算搬迁一人。
最少需要搬迁多少位居民?
输入格式
第一行两个整数 ,满足 。
接下来 行,每行一个长度为 的字符串,仅包含 . 和 #。. 表示空地,# 表示该格子住着一位居民。
输出格式
输出一个整数,表示最少需要搬迁的居民数。
样例
输入:
4 6
.##...
.#....
##....
....#.
输出:
1
搬迁第 3 行第 1 列的居民后即可修路。例如把道路交点用从 0 开始的 (行,列) 表示,可沿 (0,0)→(4,0)→(4,3)→(2,3)→(2,6)→(4,6) 行进,每段都沿现有道路。路线允许向上或向左折返,不要求单调。
