#f. Chamber of Secrets

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

基洛夫在做一个游戏。这个游戏是这样的：

一开始，矩阵左上角会发出一道光束，且一开始的方向是朝右的。基洛夫可以在一些格子摆放镜子，合理调整镜子的角度可以使得光束的方向发生变化。

基洛夫希望用尽可能少的镜子使得发射出来的光束可以到达右下角，且光束需要朝右离开矩阵。

第一行为两个数 $n,m$ ，为矩阵行列数。

往后 $n$ 行为矩阵内容，其中 # 代表可以摆放镜子的地方，. 表示不能摆放镜子的地方。

一个数，为最后需要留下来的镜子的最少个数。

如果无论如何光束也无法满足题目要求，输出 $-1$ 。

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

对于样例，选择在 $(1,2)(4,2)$ 两处摆放镜子即可。

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 1000$ 。

寒假n题