Bucket Brigade

题目描述

农场里发生了火灾，奶牛们正匆忙赶去灭火！ 农场由一个 $10 \times 10$ 的字符网格描述，如下所示： .......... .......... .......... ..B....... .......... .....R.... .......... .......... .....L.... .......... 字符 'B' 表示刚刚着火的谷仓。字符 'L' 表示湖泊，字符 'R' 表示一块大岩石的位置。 奶牛们想组成一个“传桶接力队”（bucket brigade），方法是在湖泊与谷仓之间的一条路径上站成一列，这样她们就能沿着这条路径传递装水的桶来帮助灭火。桶只能在奶牛之间传递，前提是两头奶牛在北、南、东或西方向上紧邻。对于紧邻湖泊的奶牛也同样如此——奶牛只有在与湖泊立即相邻时才能从湖泊取到一桶水。类似地，奶牛只有在与谷仓立即相邻时才能把一桶水泼到谷仓上。 请帮助确定：为了形成一条成功的传桶接力队，最少需要有多少个 '.' 格子被奶牛占据。 奶牛不能站在包含大岩石的格子上，并且保证谷仓与湖泊不会彼此立即相邻。

输入格式

输入文件包含 10 行，每行 10 个字符，描述农场的布局。

输出格式

输出一个整数，表示形成可行的传桶接力队所需的最少奶牛数量。

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

7

提示

在这个例子中，下面是一种可能的解法，使用了最优数量的奶牛（7）： .......... .......... .......... ..B....... ..C....... ..CC.R.... ...CCC.... .....C.... .....L.... .......... 题目致谢：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze