题目描述

2011年3月16日以来，利比亚爆发的骚乱不断升级，已严重危及到普通民众和各国在利比亚工作的人员的安全。为了尽快救出在利比亚的同胞，根据利比亚的形势，我国政府告诉每个在利比亚的公民，如何行动才能最快地到达安全的地方，然后由我国派出的飞机、轮船、汽车接回国。

假设利比亚的地图可以描述为一个 n 行 m 列的长方形，待拯救的同胞小 A 在 1 行 1 列处，安全的目标位置在 n 行 m 列处。小A每次只能向相邻的上、下、左、右四个方向移动，即如果小A现在的位置是 i 行 j 列，小 A 的下一步位置将到达 i-1 行 j 列、i+1 行 j 列、i 行 j-1 列、i 行 j+1 列这四个位置之一，当然小A不能移出 n 行 m 列的长方形。

利比亚是一个多沙漠且地形复杂的国家，某些位置是很危险的，人不能去。

给出利比亚的地图,请告诉小 A 从起点（1，1）走到终点（n，m）最快需要多少步呢？。

输入格式

第 1 行有 2 个正整数 n，m（1 ≤ n ≤ 2000，1 ≤ m ≤ 2000），它们之间以一个空格分隔，表示利比亚的地形可以分为 n 行 m 列。

接下来 n 行，每行 m 个字符，分别表示地图中该位置的信息。其中：

字符 “*” 表示这个位置是建筑物、河流、有地雷等人无法走到的位置（保证起点终点不是 “*” ）；

小数点 “.” 表示人可以走到该位置。

数据范围

对于 60% 的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 100；

对于 80% 的数据，1 ≤ n ≤ 250，1 ≤ m ≤ 250；

对于 90% 的数据，1 ≤ n ≤ 500，1 ≤ m ≤ 500；

对于 100% 的数据，1 ≤ n ≤ 2000，1 ≤ m ≤ 2000。

输出格式

只有一行，该行只有一个正整数。表示为小A从起点到终点，最快需要多少步。

样例

3 5
.*...
...*.
*..*.

8

样例解释

小 A 最快走法是：

1 行 1 列 → 2 行 1 列 → 2 行 2 列 → 2 行 3 列 → 1 行 3 列 → 1 行 4 列 → 1 行 5 列 → 2 行 5 列 → 3 行 5 列。