当前位置:首页 > 搜索 > 广度优先搜索 > 正文
SSOJ2229邪狼走迷宫
2310+

题目大意:在迷宫中,可以往8个方向走,从左上角走到右下角,至少需要走多少步?

题目描述

邪狼为了躲避修罗王的追捕,不得不走进一个n行m列的迷宫。迷宫入口在第1行、第1列,出口在第n行、第m列。

虽然走进迷宫,暂时安全,但是,如果不能快速走出迷宫,最终还是会被修罗王捉住,因为修罗王知道他走进迷宫了,也会尽快堵住出入口。

那么,邪狼最终能不能逃过修罗王的追捕呢?先请你来算一算邪狼穿越迷宫至少需要多少时间吧!

迷宫用0和1来描述,1代表有障碍物,0代表可以通过;邪狼在迷宫里每次移动只能从一个无障碍的单元移动到周围8个方向上任一无障碍单元,且需要消耗1个单位的时间。

输入

第一行:输入n和m两个正整数

接下来有n行,每行有m个0或1的数,每个数之间有一个空格。

输出

输出一个整数,如果可以通过迷宫,输出最少步数,否则输出0。

样例输入

4 4
0 0 0 0
1 0 1 0
1 0 0 0
1 1 1 0

样例输出

4

提示

样例说明:进入迷宫的第一步,消耗1个单位时间,接着邪狼每次往右下角方向移动,一直到出口,共需要4个单位时间。

数据范围:

40%的数据,n、m<=50

60%的数据,n、m<=100

80%的数据,n、m<=300

90%的数据,n、m<=500

100%的数据,n、m<=1000

数据保证入口和出口的位置无障碍物

解题思路

围圈防止数组越界;读入数据;起点入队并赋初值;队列不为空,出队后往8个方向走,没走过就记录步数,入队。当队列为空时,整个迷宫能走的地方都走过了,步数也出来了;如果走不到,该位置原来就是0。因此,最后直接输出步数即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2229邪狼走迷宫:等您坐沙发呢!

发表评论

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