描述
暑假即将到来,你和你的朋友计划一起去吃肯德基。城市地图上有很多肯德基餐厅(用 F 表示),你需要从中选择一家,使得从你家(@)到该餐厅的距离加上从你朋友家(&)到该餐厅的距离之和最小。如果存在多家餐厅,取距离之和最小的那家。
地图由 n 行 m 列的字符组成,字符含义如下:
- @:你的位置(起点)
- &:你朋友的位置(起点)
- F:肯德基餐厅(目标点)
- #:障碍物,不可通行
- .:空地,可以通行
你和朋友都可以在上下左右四个方向移动,每移动一格距离为 1。计算距离时,只考虑可通行的格子(即 @, &, F, .)。如果某家餐厅无法从你的位置或朋友的位置到达,则不能选择。
请计算你和朋友能够选择的最少总路程(即两人分别到同一家 KFC 的距离之和)。如果不存在任何一家 KFC 能让两人都到达,则输出 Meeting cancelled。
输入
第一行包含两个整数 $ n $ 和 $ m ( 1 \le n, m \le 500 )$,分别表示地图的行数和列数。
接下来 $ n $行,每行包含一个长度为 $ m $ 的字符串,由字符@, &, F, #, . 组成。
保证地图中恰好有一个 @ 和一个 &,且至少有一个 F。
输出
如果存在至少一家 KFC 能让两人都到达,输出一个整数,表示最小的距离之和。
否则,输出 Meeting cancelled。
样例
- 复制
- 复制
- 复制
- 复制
提示
#### 样例1解释
地图如下(行号从 1 开始):
行1: @ . # F
行2: . . . .
行3: . # . .
行4: F . . &
KFC 位于 `(1,4)` 和 `(4,1)`。
- 从 `@ (1,1)` 到 `F (1,4)` 的距离为 3(向右走三步)。
- 从 `& (4,4)` 到 `F (1,4)` 的距离为 3(向上走三步)。
- 总距离为 6。
- 从 `@` 到 `F (4,1)` 的距离为 4(向下走三步,再向左一步)。
- 从 `&` 到 `F (4,1)` 的距离为 3(向左走三步)。
- 总距离为 7。
因此最小总距离为 6,输出 6。
#### 样例2解释
地图中有两个 KFC,分别位于 `(1,4)` 和 `(4,1)`。但第二个 KFC 被障碍 `#` 阻挡,无法到达,因此只能选择 `(1,4)`。
从 `& (1,1)` 到 `F (1,4)` 的距离为 3。
从 `@ (4,4)` 到 `F (1,4)` 的距离为 5(向上走三步,向左一步,再向上一步?实际路线为 (4,4)->(3,4)->(2,4)->(2,3)->(2,2)->(1,2)->(1,3)->(1,4) 共7步?让我们计算:从 (4,4) 到 (1,4) 不能直接向上,因为有障碍吗?地图第2行第4列是'.',第3行第4列是'.',所以从 (4,4) 向上三步到 (1,4) 经过 (3,4),(2,4),(1,4) 都是可通行的,距离为3。但输出为8,说明可能路线需要绕行。实际上样例输出是8,因此最小总距离为8。
## 数据范围与约定
- $ 1 \le n, m \le 500 $
- 地图中恰好有一个 `@` 和一个 `&`。
- 至少有一个 `F`。
- 障碍物 `#` 不可通行。

关注我们