【题目描述】

给你一个 $n$ 行 $n$ 列的包含 0, 1 的矩阵，0 表示空地，1 表示障碍。起点为左上角 $(1, 1)$ 位置，终点为右下角 $(n, n)$ 位置，每次只能向右走、向下走、向左走、向上走：假如当前在位置 $(i, j)$，你只能走到 $(i, j+1)$、$(i+1, j)$、$(i, j-1)$、$(i-1, j)$ 位置。

每个位置每个单位时间都会变换状态，例如 $(i, j)$ 在第 $k$ 个单位时间是空地，则在第 $k+1$ 个单位时间是障碍。$(i, j)$ 在第 $k$ 个单位时间是障碍，则在第 $k+1$ 个单位时间是空地。

保证起点的初始状态是空地。保证起点出发可以到达终点。 问起点到终点的最短时间。

注意：

1. 行走过程中，不能在某个点上逗留。
2. 不论自身所在位置是空地还是障碍，只要下一步到达的位置是空地，那么这个位置就能走。

【输入格式】

从文件 maze.in 中读入数据。 第一行一个正整数 $n$。 接下来 $n$ 行，每行一个长度为 $n$ 的整数序列，描述这个矩阵。

【输出格式】

输出到文件 maze.out 中。 一行一个数，表示答案。

【样例 1 输入】

3
0 0 0
1 0 1
0 1 0

【样例 1 输出】

4

【样例 2 输入】

3
0 0 0
1 0 0
0 1 0

【样例 2 输出】

4

大样例

【数据范围】

• 对于测试点 1 ∼ 4：$1 \le n \le 10$；
• 对于测试点 5 ∼ 8：$1 \le n \le 100$；
• 对于测试点 9 ∼ 10：$1 \le n \le 1000$。