Skip to content

1035: 酒吧

题目

题目描述

莘庄有很多酒吧,侯不会和苏前端打算约在其中一个酒吧见面。为了节省时间,他们希望从各自的家赶往酒吧的时间之和尽可能少,现在请你为他们挑选一个酒吧。莘庄可以被划分为$n \times m$个单元格,每个单元格可能是侯不会的家('H')、苏前端的家('S')、障碍物('#')、空地('.')或者酒吧('B'),其中障碍物所在位置不能通行,其余单元格均可通行,保证至少有一个酒吧两人都可以到达。侯不会和苏前端每分钟可以向上下左右移动一格。求侯不会和苏前端各自从家到酒吧的时间之和的最小值。

输入格式

第一行包含两个整数n, m。($2 \le n, m \le 1000$)

接下来n行,每行有m个用空格隔开的字符。

'H'代表侯不会的家的位置。

'S'代表苏前端的家的位置。

'#'代表障碍物的位置。

'.'代表可通行的位置。

'B'代表酒吧的位置。

输出格式

一个整数,表示侯不会和苏前端各自从家到酒吧的时间之和的最小值。

样例输入

4 4 H.#B .... .#.. B..S

样例输出

6

数据范围

对于20%的数据,$2 \le n, m \le 20$。

对于另外20%的数据,地图上没有障碍物。

对于另外20%的数据,地图上只有一个酒吧。

对于100%的数据,$2 \le n, m \le 1000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!