USACO 2019 US Open Contest, Bronze Problem 1 Bucket Brigade
A fire has broken out on the farm, and the cows are rushing to try and put it out!
The farm is described by a 10×1010×10 grid of characters like this:
.......... .......... .......... ..B....... .......... .....R.... .......... .......... .....L.... ..........
The character 'B' represents the barn, which has just caught on fire. The 'L' character represents a lake, and 'R' represents the location of a large rock.
The cows want to form a "bucket brigade" by placing themselves along a path between the lake and the barn so that they can pass buckets of water along the path to help extinguish the fire. A bucket can move between cows if they are immediately adjacent in the north, south, east, or west directions. The same is true for a cow next to the lake --- the cow can only extract a bucket of water from the lake if she is immediately adjacent to the lake. Similarly, a cow can only throw a bucket of water on the barn if she is immediately adjacent to the barn.
Please help determine the minimum number of '.' squares that should be occupied by cows to form a successful bucket brigade.
A cow cannot be placed on the square containing the large rock, and the barn and lake are guaranteed not to be immediately adjacent to each-other.
INPUT FORMAT (file buckets.in):
The input file contains 10 rows each with 10 characters, describing the layout of the farm.
OUTPUT FORMAT (file buckets.out):
Output a single integer giving the minimum number of cows needed to form a viable bucket brigade.
SAMPLE INPUT:
.......... .......... .......... ..B....... .......... .....R.... .......... .......... .....L.... ..........
SAMPLE OUTPUT:
7
In this example, here is one possible solution, which involves the optimal number of cows (7):
.......... .......... .......... ..B....... ..C....... ..CC.R.... ...CCC.... .....C.... .....L.... ..........
Problem credits: Brian Dean
中文版
农场上起火了，奶牛们正在紧急赶去灭火！
农场可以用一个像这样的10×1010×10的字符方阵来描述：
.......... .......... .......... ..B....... .......... .....R.... .......... .......... .....L.... ..........
字符'B'表示正着火的牛棚。字符'L'表示一个湖，而字符'R'表示农场上的一块巨大岩石。
奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。这对于湖边的奶牛也是对的——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。
请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的'.'格子的最小数量。
奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。
输入格式（文件名：buckets.in）：
输入包含10行，每行10个字符，描述这个农场的布局。输入保证图案中恰有一个字符'B'、一个字符'L'以及一个字符'R'。
输出格式（文件名：buckets.out）：
输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。
输入样例：
.......... .......... .......... ..B....... .......... .....R.... .......... .......... .....L.... ..........
输出样例：
7
在这个例子中，以下是一个可行的方案，使用了最小数量的奶牛（7）：
.......... .......... .......... ..B....... ..C....... ..CC.R.... ...CCC.... .....C.... .....L.... ..........
供题：Brian Dean
国际竞赛真题资料-点击免费领取！
美高学分项目重磅来袭！立即了解
AMC8备考管家服务全新上线！
