魔法网格

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有一个 \(n × n\) 的网格，网格上的每个格子中有一个数字，为0,1,2三个数字之一。

　　你现在要从网格的左上角走到右下角。任何一个时刻，你所站的网格必须是0或1，并且你只能向上、下、 左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的数字同为0或同为1，那你不需要代价；如果不同，则你需要付出1个单位的代价。

　　另外，你需要额外花费 2 个单位的代价施展魔法让下一个数字为2的格子暂时变为0或1。但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法走一步之后走到了新格子，下一步就不能使用魔法；只有当你不使用魔法离开这个新格子的时候，下一步能继续使用这个魔法，而当你离开了这个施展魔法的新格子时，这个格子马上恢复到原来的数字。

　　现在你最少需要多少代价才能要从网格的最左上角走到右下角？

【输入格式】

　　数据的第一行包含两个正整数 \(n\)，代表网格的大小。接下来 \(n\) 行每行包含 \(n\) 个数字（0,1或2），表示对应网格的数字。输入保证网格的左上角，也就是 \((1,1)\)一定是数字0或1。

【输出格式】

　　输出一个整数，表示最小的花费，如果无法到达，输出-1。

【输入输出样例1】

　Input

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

　Output

8

【输入输出样例1说明】

　　从（1，1）开始，走到（1，2）无代价；
　　从（1，2）向下走到（2，2）花费 1 个单位的代价；
　　从（2，2）施展魔法，将（2，3）变为数字1，花费 2 个单位的代价；
　　从（2，2）走到（2，3）无代价；
　　从（2，3）走到（3，3）无代价；
　　从（3，3）走到（3，4）花费 1 个单位的代价；
　　从（3，4）走到（4，4）花费 1 个单位的代价；
　　从（4，4）施展魔法，将（4，5）变为数字1，花费 2 个单位的代价；
　　从（4，4）走到（4，5）无代价；
　　从（4，5）走到（5，5）花费 1 个单位的代价；
　　共花费 8 无代价。

【输入输出样例2】

　Input

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

　Output

-1

【数据规模与约定】

　　对于 \(30\%\) 的数据，\(1 ≤ n ≤ 5\)。
　　对于 \(60\%\) 的数据，\(1 ≤ n ≤ 20\)。
　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 100\)。

【来源】

　　Mr.he