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

---

【题目描述】

　　FJ搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口，并且从迷宫中的任意一点都能找到一条走出迷宫的路。给定迷宫的行和列数和这个迷宫，然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的最少步数。

【输入格式】

　　第一行为正数 \(m\) 和 \(n\)，表示迷宫的行数和列数，用空格隔开。迷宫用一个由数字组成的矩阵表示，一个数字表示迷宫的一个格子。每一个格子的数字告诉我们这个格子的东、西、南、北是否有栅栏存在。每个数字是由以下四个整数的某个或某几个或一个都没有加起来的。 　　
　　1: 在西面有栅栏　　
　　2: 在北面有栅栏　　
　　4: 在东面有栅栏　　
　　8: 在南面有栅栏
　　迷宫内部的栅栏会被规定两次。比如说(1,1)南面的栅栏，亦会被标记为(2,1)北面的栅栏。

【输出格式】

　　输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。

【输入输出样例】

　Input

3 5
11 2 10 2 6
3 8 14 5 5
13 3 10 12 9

　Output

9

【样例解释】

　　下图是样例给出迷宫图，其中一种最糟糕的那个点走出迷宫步数最少的走法如下：

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤m≤38\)，\(1≤n≤100\)。

【来源】

　　Mr.he