shunfurh
编程介的小学生
2017-09-30 06:26

三足鼎立

  • 数据
  • 地图
  • 测试
  • x

Problem Description
  “纷纷世事无穷尽,天数茫茫不可逃。鼎足三分已成梦,后人凭吊空牢骚。”

  三国的各种传奇故事被千百年传诵,为人们津津乐道。魏、蜀、吴三个势力相互制约,同时也相互利用,“三”的神奇和精妙尽在其中。于是,这个问题也是关于“三”的。

  在一个N * M的地图上,两个点(x1, y1)和(x2, y2)之间的距离被定义成曼哈顿距离,魏、蜀、吴三个势力要在这个地图上分别选择自己的据点。由于地图上某些点已经被其他势力占据,为了避免不必要的冲突,他们希望自己的据点与其他被占据的点都可以保持一定的距离,包括他们三个势力据点的相互距离,也要满足约束。

  现在,三个势力不可思议的开了一次首脑峰会,商谈据点的安排问题。你,作为一个像鲁肃大师一样爱好和平的外交家,要给出最大的限制距离,使得至少有一种安排方案满足条件。

Input
输入第一行为T,表示有T组测试数据。
每组数据以两个整数N和M开始,表示地图的规模。接下来的N行,每一行包含一个长度为M的字符串,表示地图,‘.’表示空地,’F’表示这里已被其他势力占据。地图至少有三个空格以供选择。

[Technical Specification]
1. 1 <= T <= 74
2. 1 <= N, M <= 74

Output
对每组数据,先输出为第几组数据,然后输出最大限制距离。

Sample Input
2
4 4
F...
....
....
....
4 4
F..F
....
....
F..F

Sample Output
Case 1: 3
Case 2: 1

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

3条回答

为你推荐