珂朵莉与斯卡布罗集市

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

        斯卡布罗集市是一个非常繁华的集市,这里有很多有名的景点。为了防止迷路,威廉买了一张集市的地图,地图长 m 宽 n ,其中 “1” 代表他们目前的位置,“0” 代表空地,其他数字分别代表不同的景点(每个景点的编号均不同且每个景点在地图上只出现一次)。

        现在珂朵莉想要知道从当前位置到距离编号为 x 的景点在地图上的最短距离是多少(在地图上只能沿与坐标平行的方向移动,图中的每一个点都可以走),你能帮帮他么?

Input

        多组输入,每组数据第一行两个数字 n , m 代表地图的宽和长( 1<= n, m<= 100) 。

        接下来的 n 行每行 m 个数(空格分隔)代表地图。

        最后输入一个数字 x 代表珂朵莉想要去的景点编号( 2<= x<= 1000)。

Output

        输出当前位置距离想去的景点在地图上的最短距离(在地图上只能沿与坐标平行的方向移动)

Sample Input

3 3
0 1 2
3 0 0
6 4 9
6

Sample Output

3

Hint

在计算地图上的最短距离时结果仅与两点坐标有关而不会因为其他景点的阻隔而绕路,对于样例:

( 1, 2 ) -> ( 2, 2 )

( 2, 2 ) -> ( 3, 2 )

( 3, 2 ) -> ( 3, 1 )

因此答案是 2 + 1 ,三步。

Source

行走的二叉树