← 返回题目列表

Codeforces · 173/B

B. 密室

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

“密室再次被打开”——这个消息传遍了霍格沃茨,一些学生因为看到了蛇怪而被吓呆了。邓布利多被解雇了,现在哈利正试图进入密室。这对伏地魔来说可不是什么好消息。问题是,他不希望任何人能够进入房间。黑魔王将忙着吸干金妮的生命。

密室是一个 n × m 的矩形网格,其中一些单元格是列。光线(以及蛇怪的凝视)穿过柱子而不改变其方向。但是通过一些咒语,我们可以使柱魔法在接收到光线时将光线(或凝视)反射到所有四个方向。如下图所示。

左侧光线穿过常规柱,右侧光线穿过魔法柱。

蛇怪位于网格右下单元格的右侧,并且向左看(沿着左下单元格的方向)。根据传说,任何人直接与蛇怪凝视都会立即死亡。但如果有人透过柱子与蛇怪的目光相遇,这个人就会被石化。我们知道密室的门位于网格左上角的左侧,任何想要进入的人都会从该位置向其移动方向(右上角单元格的方向)看。

该图说明了第一个示例测试。

考虑到密室的尺寸和常规柱子的位置,伏地魔要求你找到我们制造魔法所需的最小柱子数量,这样任何想要进入密室的人都会被吓呆,或者只是宣布不可能保护密室。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 1000)。接下来的 n 行每行包含 m 个字符。每个字符都是“.”。或“#”并代表腔室网格的一个单元格。它是 ”。”如果相应的单元格为空,则为“#”,如果它是常规列。

输出

打印产生魔法的最小列数,如果不可能,则打印 -1。

示例

输入 #1

3 3
.#.
...
.#.

输出 #1

2

输入 #2

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

输出 #2

2

注意

上图显示了第一个样本测试。在第一个示例中,我们应该使两列都变得神奇。龙代表蛇怪,双筒望远镜代表将进入密室的人。黑色的星辰,代表着人会被石化的地方。黄线代表蛇怪的目光穿过柱子。