题目描述

小童参加一个寻宝游戏，主办方给定一个n * n的迷宫，在迷宫中某个位置放置奖品，所有参赛选手都从左上角(1,1)出发，谁先找到奖品就归谁。 移动中规定选手除了上下左右移动，还可以从当前坐标(x,y)移动到(2 * x , 2 * y)的位置。 请帮助小童最快找到宝藏，输出移动步数。

输入格式

第一行一个整数n（n<=50）,表示迷宫的大小。 下面是一个n * n的迷宫。‘.’表示安全；‘*’表示剧毒迷雾；‘$’表示奖品。

输出格式

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

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

2