问题6401--水桶传递

6401: 水桶传递

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

农场上起火了,奶牛们正在紧急赶去灭火!

农场可以用一个像这样的10×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

输入

输入包含10行,每行10个字符,描述这个农场的布局。输入保证图案中恰有一个字符'B'、一个字符'L'以及一个字符'R'

输出

输出一个整数,为组成一条可行的水桶传递队列所需要的奶牛的最小数量。

样例输入 复制

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

样例输出 复制

7

提示

在这个例子中,以下是一个可行的方案,使用了最小数量的奶牛(7):

..........

..........

..........

..B.......

..C.......

..CC.R....

...CCC....

.....C....

.....L....

..........

来源/分类