← 返回题目列表

Codeforces · 1214/D

D. 金银岛

中文机器翻译题面 查看原题

我们都喜欢宝藏,对吗?这就是年轻的瓦夏前往金银岛的原因。

金银岛可以表示为一张被海洋包围的矩形桌子 $$$n \times m$$$。让我们从上到下对字段中具有从 $$$1$$$ 到 $$$n$$$ 的连续整数的行进行编号,并从左到右对具有从 $$$1$$$ 到 $$$m$$$ 的连续整数的列进行编号。将 $$$r$$$ 行和 $$$c$$$ 列中的单元格表示为 $$$(r, c)$$$。一些岛屿单元包含无法通行的森林,而一些单元是免费且可通行的。宝藏隐藏在单元格$$$(n, m)$$$中。

Vasya 在 $$$(1, 1)$$$ 牢房下船。现在他想要到达宝藏。他速度很快,所以他只能从单元格移动到下一行(向下)或下一列(向右)的单元格,即从单元格 $$$(x, y)$$$ 他只能移动到单元格 $$$(x+1, y)$$$ 和 $$$(x, y+1)$$$。当然,瓦夏无法穿过森林无法通行的牢房。

邪恶女巫知道了瓦西亚的旅程,她将阻止他到达宝藏。在瓦西亚采取第一步行动之前,她能够使用她的邪恶魔法在以前空闲的牢房中生长不可通行的森林。女巫能够在任意数量的任意单元格中种植森林,除了 Vasya 下船的单元格 $$$(1, 1)$$$ 和隐藏宝藏的单元格 $$$(n, m)$$$ 之外。

帮助邪恶女巫找出她必须将多少格子变成无法通行的森林,以便瓦夏不再能够到达宝藏。

输入

输入的第一行包含两个正整数 $$$n$$$、$$$m$$$ ($$$3 \le n \cdot m \le 1\,000\,000$$$),即岛屿的大小。

以下 $$$n$$$ 行包含描述岛屿的长度为 $$$m$$$ 的字符串 $$$s_i$$$,如果单元格 $$$(i, j)$$$ 包含不可通行的森林和“.”,则字符串 $$$s_i$$$ 的第 $$$j$$$ 个字符等于“#”。如果小区空闲并且可以通过。让我们提醒您,Vasya 在单元格 $$$(1, 1)$$$ 下船,即第一行的第一个单元格,他想要到达单元格 $$$(n, m)$$$,即最后一行的最后一个单元格。

可以保证单元格 $$$(1, 1)$$$ 和 $$$(n, m)$$$ 为空。

输出

打印唯一的整数$$$k$$$,这是邪恶女巫为了阻止Vasya到达宝藏而必须变成无法通行的森林的最小单元格数量。

示例

输入 #1

2 2
..
..

输出 #1

2

输入 #2

4 4
....
#.#.
....
.#..

输出 #2

1

输入 #3

3 4
....
.##.
....

输出 #3

2

注意

下图展示了第三个示例中的岛屿。蓝色箭头显示 Vasya 可能使用的从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 的可能路径。红色表示女巫可能将一组单元变成无法通行的森林,从而使 Vasya 从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 的旅程变得不可能。