portal

题号：NC202588
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛最近完了一款名叫传送门的游戏，但是他不满足于只是通关，他希望找到每一关的最佳通关方式。

游戏是在一个N*N的网格图中进行的，图中的网格分为四种类型，0表示空地可以通过，1表示墙壁无法通过，2表示不仅可以通过，还可以在该格放置一个传送门，3表示有且仅有的唯一的固定传送门。

在游戏开始时，牛牛可以选择一块2类型的格子放置传送门并且不可以中途更改，在游戏过程中，如果到达其中一个传送门，则可以传送往另一个传送门。游戏的起点始终为左上角，终点始终为右下角，牛牛每次可以往四个方向移动，即上下左右四个方向。牛牛想知道从起点走到终点最少需要走几步（使用传送门也算作一步）。

返回：最少的需要走的步数。

示例1

输入

复制

6,[[0,0,3,0,0,0],[0,0,0,2,2,0],[1,1,1,2,1,0],[2,1,0,0,0,0],[0,0,0,0,0,1],[0,1,1,1,0,0]]

返回值

复制

备注:

保证地图中有且仅有一个标为3的格子，不保证一定有标为2的格子。
无论是否放置传送门，标为3的格子和标为2的格子都可以正常通过。
保证一定存在可行方案。
样例的直观图为:
0 0 3 0 0 0
0 0 0 2 2 0
1 1 1 2 1 0
2 1 0 0 0 0
0 0 0 0 0 1
0 1 1 1 0 0