问题 F: 给力台球厅

问题 F: 给力台球厅

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

教练爱打台球。这天偶遇一家台球厅,便进去看看。然而这家台球厅貌似和平常的台球厅不太一样,它的每张桌面上的洞都是随机分布在桌面上的,球也是随机摆放的。

教练立即意识到,此台球厅的桌面不符合正态分布之概率密度函数,而是呈离散分布,顿时患有强迫症的教练心里就不舒服了。为了平缓一下翻腾的内心,教练随机选取了一张球和洞数量一样的球桌,望着奇怪的桌面与奇怪的球,教练脑袋上不禁长出了大把大把的草:如果能求出所有球入洞的最短距离之和该有多好啊。

现有一个桌面面积为 n×m 的台球桌,将台球桌分成 n×m 个小格,台球桌上有许多的洞和许多的球,均匀分布在小格里,且每个小格只有三种状态,有球,有洞,空白。球用 @ 表示,洞用 # 表示,空白的地方用 * 表示。每个洞只能容纳一个球,球每次只能按照上下左右的方向移动,且每移动一格视为移动 1 个单位长度。当一个球被另一个球挡住时,它可以跳球,所以每一个球都可以完全无视其他球或洞的存在而继续前行,直到进自己心仪的洞。现求所有球进洞的距离之和最小是多少。如果你能帮教练解决这道题,恭喜你就是 ACM 队员了(每个球只能进一个洞,每个洞内有球的话就变成空白状态)

输入

多组测试样例,首行输入 m,n,即矩形台球桌面的边长。(2 ≤ m,n ≤ 20,球最多100个,洞最多100个,保证洞和球数量相等)

输出

输出一个整数,即所有球入洞的距离最短是多少。

样例输入

2 2
*#
@*
7 8
****#***
****#***
****#***
@@@@#@@@
****#***
****#***
****#***

样例输出

2
28
[提交][状态]