题目描述

给定一个规模为 $n$（$n$行$n$列）的迷宫（四面有墙），从起点出发，每次只能向上下左右四个方向移动一步，求从起点移动到终点所需的最少步数。

输入格式

第一行迷宫规模 $n$;

从第二行起输入 $n$ 行 $n$ 列的迷宫地图。

其中 $0$ 表示障碍物，$6$ 表示起点，$8$ 表示终点，$1$ 表示可行的格子。

输出格式

最少步数

样例

5
1 6 0 8 1
1 0 0 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1

8

数据范围

对100%的数据，$0 \lt n \le 10000$​​。