name:小埋迷宫作业

时间限制: 2000ms 空间限制: 65536kB

题目描述

众所周知，小埋是一个准时完成作业的优秀同学。但是小埋在做梦写作业，遇到一个迷宫，上面指示描述作业就在迷宫之中，你必须从迷宫中找到这个作业，然后完成它。对于小埋同学来说，写作业是很简单的一件事情，但是从迷宫中找到作业却很困难，现在请你帮小埋从迷宫中找到该作业。

小埋从 （1,1）（1,1） 开始，每秒可以向上下左右某一方向走2的次方步，请你帮助小埋用最少的时间找到该作业。

输入格式

第一行两个整数 n，m

接下来 n行，每行 m 个字符,$ 或者 . 表示可走的空地，X 表示障碍，#表示作业。（保证只有一个作业）

输出格式

小埋到达作业最短耗时。如果没有解输出-1。

样例

输入:

2 2
$$
.#

输出:

2

1<=n,m<=1000