当前位置:首页 > 搜索 > 广度优先搜索 > 正文
SSOJ2315营救
3972+

题目大意:给出一个用0和1代表陆地还海洋的地图,问从某个位置到某个位置的最短路径是多少?

题目描述

铁塔尼号遇险了!他发出了求救信号。距离最近的哥伦比亚号收到了讯息,时间就是生命,必须尽快赶到那里。

通过侦测,哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位,其中用1标明的是陆地,用0标明的是海洋。船只能从一个格子移到相邻的四个格子。

为了尽快赶到出事地点,哥伦比亚号最少需要走多远的距离?

输入

第一行为n,下面是一个n*n的0、1矩阵,表示海洋地图。(n<=1000)

最后一行为四个小于n的整数,分别表示哥伦比亚号和铁塔尼号的位置。

输出

哥伦比亚号到铁塔号的最短距离,答案精确到整数。

样例输入

3
001 
101 
100
1 1 3 3

样例输出

4

解题思路

一个一个填格子,广度优先!因为深度优先,不能保证填进去的步数是最少步数,会导致重复搜索,效率极低,严重超时。

读入数据前,先让地图全是非0的数,这样就可以避免搜索过程中走到地图外面出现数组越界等错误。由于需要存储位置(坐标),可以开两个队列数组分别存储x和y,为了节省空间,我们可以把(x,y)转成一个k(如1005)进制数,即转成z=x*k+y,变回去的时候x=z/k,y=z%k。只有这个k比行号大就不会出现冲突了。

接下来就是裸的广搜:逐个出队,往4个方向试探,能走且没走过,就走下去,记录下一个位置的步数是当前位置步数加1,入队。直到队列为空或者到达目的地,搜索结束。输出时,由于起点是第1步(避免走回起点),题目不算起点那个位置,所有答案要减1。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2315营救:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!