首页 / 题库

P14065 - 相约KFC

算法入门
通过次数18 提交次数62 内存限制 128MB 时间限制1秒

描述

暑假即将到来,你和你的朋友计划一起去吃肯德基。城市地图上有很多肯德基餐厅(用 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`。
- 障碍物 `#` 不可通行。

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36