SSOJ2229邪狼走迷宫
2842+
作者：crxis 发布：2017-08-28 分类：广度优先搜索
题目大意：在迷宫中，可以往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。因此，最后直接输出步数即可。
程序实现
