2453: 迷宫寻宝

题目描述

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

输入描述

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

输出描述

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