2454: 棋盘游戏

题目描述

小童在玩一个n*n的棋盘游戏，他除了自己的将棋，只剩下了一枚在(1,1)位置的棋子。
请你计算这枚棋子，最少用几步到达对方帅棋的位置。
注意：如图所示，该棋子每次移动有8个方向可供选择。

输入描述

第一行一个整数n（n<=50），表示棋盘的规模。
下面是一个n*n的矩阵，0表示可以通过，1表示无法通过，#表示对方帅棋。

输出描述

如果棋子能移动到对方帅棋，输出最少的步数；不能则输出-1。