题目描述

给你一个 $n$ 行 $m$ 列的字符矩阵，其中 . 表示平地，# 表示障碍物，你每次可以按照上下左右四个方向行走，问你从左上角（第 $1$ 行第 $1$ 列）走到右下角（第 $n$ 行第 $m$ 列）最少需要多少步？
请输出最少需要的步数，如果走不到，请输出 $-1$。
（保证起点和终点没有障碍物）

输入格式

第一行两个整数 $n,m$。
接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述这个字符矩阵。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

5 5
.####
.....
####.
####.
####.

输出 #1

8

说明/提示

$1\le n,m\le 1000$。