题目背景

打败怪物后，王老师来到一个古老的网格迷宫，传说中的算法卷轴就藏在迷宫深处。

题目描述

迷宫是一个 $R \times C$ 的网格。王老师在起点 $(1, 1)$，要前往终点 $(R, C)$ 寻找算法卷轴。迷宫中有些格子是空地（用 . 表示），有些是陷阱（用 # 表示）。王老师每次可以向上下左右四个方向移动一格。求王老师到达终点的最少步数。如果无法到达，输出 -1。

输入格式

第一行两个整数 $R, C$，表示迷宫的行数和列数。 接下来 $R$ 行，每行一个长度为 $C$ 的字符串，表示迷宫的地形。

输出格式

一个整数，表示最少步数。若无法到达终点输出 -1。

样例输入

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

样例输出

5

数据规模

对于 100% 的数据，$1 \le R, C \le 1000$