SZ#G4M11. 【GESP强化 四级】校园传水

提交3 通过1
通过率33.3%
时间限制1000ms
内存限制256MiB
    ID: 10687 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 普及- 上传者: 标签>GESPGESP强化C++c++编程题二维数组二维坐标曼哈顿距离分类讨论

题目描述

校园的一处设备点发生了火情,学员们准备从取水点排成一支传水队。场地用固定的 10×1010\times10 字符地图表示:B 表示需要灭火的设备点,L 表示取水点,R 表示不能通过的大型障碍物,. 表示可以站立的空格。

传水时,只有站在上、下、左、右方向相邻方格中的两名学员之间才能传递水桶;队伍一端的学员必须与取水点相邻,另一端的学员必须与设备点相邻。

障碍物所在的方格不能站人,并且设备点与取水点保证不相邻。刘老师需要知道在 . 方格中至少安排多少名学员,才能形成一条完整可行的传水队。

输入格式

输入 1010 行,每行 1010 个字符,描述校园场地。地图中恰好有一个 B、一个 L 和一个 R,其余均为 .

输出格式

输出形成可行传水队所需的最少学员数量。

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
7
B.......L.
..........
..........
..........
....R.....
..........
..........
..........
..........
..........
7
B...R...L.
..........
..........
..........
..........
..........
..........
..........
..........
..........
9

样例解释

  • 样例 1 中,最优传水队需要 77 名学员;他们可以绕开障碍物,用上下左右相邻的方格连接取水点与设备点。
  • 补充样例中,设备点和取水点同行,障碍物不在两者之间,直接连接即可。
  • 补充样例中,障碍物位于设备点和取水点之间,传水队必须向旁边绕行两步。

数据范围与约定

  • 地图固定为 10×1010\times10
  • BLR 各出现一次
  • BL 不在上下左右方向上相邻