【rqnoj34】紧急援救

2013年11月12日1,4690

题目描述

话说2007年8月5日,Mike博士神秘失踪了,最后发现是被外星人绑架了,幸好外星人目前还是在地球上活动,并且知道外星人不了解地球,幸好,Milk博士身上有无线信号发送装置,我们终于确定了他的位置,必须赶快到那里去救他。

根据无线信号发送装置,我们确定出一张地图,为了尽快寻找到Mike博士,于是这个光荣和艰巨的任务便交给了你,编写程序,通过使用一张地图帮助研究所确定从研究所出发找到Mike博士最短距离。

数据范围: n<=1000

输入格式第一行为n

第二行为n*n的地图(其中0表示通路,1表示死路)

最后两行每行有两个数字,分别表示研究所的坐标和博士信号所在的位置。

输出格式一个数字k,表示从研究所出发找到Milk博士的最短距离。

样例输入

10
0100110100
0001110010
1000000001
1000100011
0000101100
1000001100
1001010011
0000010100
0101010000
1001000001
1 7
10 2

样例输出

14