棋盘游戏

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

输入格式

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

输出格式

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

5
00000
01010
01000 
00#10
10110

4

数据范围

时间限制: 1000ms

内存限制: 256MB