迷宫寻宝

题目描述

小童参加一个寻宝游戏，主办方给定一个 $n \times n$ 的迷宫，在迷宫中某个位置放置奖品，所有参赛选手都从左上角 $(1,1)$ 出发，谁先找到奖品就归谁。

移动中规定选手除了上下左右移动，还可以从当前坐标 $(x,y)$ 移动到 $(2x, 2y)$ 的位置。

请帮助小童最快找到宝藏，输出移动步数。

输入格式

第一行一个整数 $n$（$n \le 50$），表示迷宫的大小。

下面是一个 $n \times n$ 的迷宫，句号表示安全；星号表示剧毒迷雾；美元符号表示奖品。

输出格式

一个整数，表示最少移动步数；无法到达输出-1。

样例输入 #1

4
...*
...*
.*..
..*$

样例输出 #1

2

数据范围

$n \le 50$。

知识点与难度

本题涉及的知识点从属于 GESP六级（搜索基础、BFS），难度等级：⭐⭐。

测试点分布