“密室再次被打开”——这个消息传遍了霍格沃茨,一些学生因为看到了蛇怪而被吓呆了。邓布利多被解雇了,现在哈利正试图进入密室。这对伏地魔来说可不是什么好消息。问题是,他不希望任何人能够进入房间。黑魔王将忙着吸干金妮的生命。
密室是一个 n × m 的矩形网格,其中一些单元格是列。光线(以及蛇怪的凝视)穿过柱子而不改变其方向。但是通过一些咒语,我们可以使柱魔法在接收到光线时将光线(或凝视)反射到所有四个方向。如下图所示。
左侧光线穿过常规柱,右侧光线穿过魔法柱。
蛇怪位于网格右下单元格的右侧,并且向左看(沿着左下单元格的方向)。根据传说,任何人直接与蛇怪凝视都会立即死亡。但如果有人透过柱子与蛇怪的目光相遇,这个人就会被石化。我们知道密室的门位于网格左上角的左侧,任何想要进入的人都会从该位置向其移动方向(右上角单元格的方向)看。
该图说明了第一个示例测试。
考虑到密室的尺寸和常规柱子的位置,伏地魔要求你找到我们制造魔法所需的最小柱子数量,这样任何想要进入密室的人都会被吓呆,或者只是宣布不可能保护密室。
输入
输入的第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 1000)。接下来的 n 行每行包含 m 个字符。每个字符都是“.”。或“#”并代表腔室网格的一个单元格。它是 ”。”如果相应的单元格为空,则为“#”,如果它是常规列。
输出
打印产生魔法的最小列数,如果不可能,则打印 -1。
示例
输入 #1
3 3 .#. ... .#.
输出 #1
2
输入 #2
4 3 ##. ... .#. .#.
输出 #2
2
注意
上图显示了第一个样本测试。在第一个示例中,我们应该使两列都变得神奇。龙代表蛇怪,双筒望远镜代表将进入密室的人。黑色的星辰,代表着人会被石化的地方。黄线代表蛇怪的目光穿过柱子。