棋盘游戏

题目描述

小童在玩一个 $n \times n$ 的棋盘游戏，他除了自己的将棋，只剩下了一枚在 $(1,1)$ 位置的棋子。

请你计算这枚棋子，最少用几步到达对方帅棋的位置。

注意：该棋子每次移动有 8 个方向可供选择。

输入格式

第一行一个整数 $n$（$n \le 50$），表示棋盘的规模。

下面是一个 $n \times n$ 的矩阵，0 表示可以通过，1 表示无法通过，# 表示对方帅棋。

输出格式

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

样例输入 #1

5
00000
01010
01000
00#10
10110

样例输出 #1

4

样例输入 #2

5
00000
01010
01000
00111
1001#

样例输出 #2

-1

数据范围

$n \le 50$。

知识点与难度

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

测试点分布