OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题1221--广度优先遍历

1221: 广度优先遍历

时间限制: 1 Sec  内存限制: 128 MB
提交: 61  解决: 20
[提交] [状态] [讨论版] [命题人:]

题目描述

很多人小时候都玩过泡泡堂,那是一个在平面图当中,通过放定时水炸弹,炸毁建筑物获取道具,或者是将敌人封装到水球里的游戏,经典的玩法和可爱的画风,成为了一代人不可磨灭的童年回忆。游戏当中有许多角色,皮蛋、宝宝、黑妞、小强、胖墩……一天,皮蛋去找黑妞玩儿,突然村里发来紧急通知,海盗船长jzl刚刚来过泡泡村,还埋下了许多水地雷,只要踩到就会被封住,任人羞辱,皮蛋掏出羊皮卷,神奇的羊皮卷可以显示整个泡泡村的平面地形,通过观察,他已经得知哪些地方有水地雷,现在他要以最快的速度跑去仓库,找来工具拆除地雷。皮蛋数学很差,只能从1数到2,无法计算到达的时间,于是村长ghx找到了你,作为村里的数学鬼才,请你帮村长解决这个问题吧!
 

输入

第一行两个整数N, M(1 <= N, M <= 1000),接下来第2行到第N + 1行,每行M个字符Aij,Aij为 “#” 表示该点是水地雷,Aij “.”表示该点为陆地,第N + 2行输入四个整数sx,sy,ex,ey(1 <= sx, ex <= N; 1 <= sy, ey <= M),(sx,sy)表示起点坐标,(ex,ey)表示仓库坐标,保证起点和仓库处不会有水地雷。(只能走上下左右四个方向)。 

输出

一个整数占一行,表示从起点到仓库的最小时间花费,如果无法到达仓库,输出“Bang”(不带引号) 

样例输入 Copy

4 6
..#...
#...#.
#.###.
#.....
1 1 4 3

样例输出 Copy

5

来源/分类

图论