悟空救师傅

题目描述

取经路上师傅被妖怪抓走了，悟空前去营救，他发现妖怪的洞穴是一个类似 $n \times n$ 的矩阵，悟空站在 $(1,1)$ 的位置，过程中只能向上下左右 $4$ 个方向移动。

请你计算悟空最少几步可以找到师傅。

输入格式

第一行一个整数 $n$，表示矩阵的规模。

下面是一个 $n \times n$ 的矩阵，$0$ 表示可以通过，$1$ 表示无法通过，$2$ 表示师傅，空格分隔。

输出格式

一个整数，能找到师傅输出最少步数；不能找到师傅输出 $-1$。

样例输入 #1

5
0 0 0 0 0
0 1 0 1 2
0 1 0 0 0
0 0 0 1 0
1 0 1 1 0

样例输出 #1

5

样例输入 #2

5
0 0 0 0 0
1 0 0 1 0
2 1 0 0 0
1 0 0 1 0
1 0 1 1 0

样例输出 #2

-1

数据范围

$1 \le n \le 50$。

知识点与难度

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

测试点分布