编程介的小学生 2017-09-30 06:26 采纳率: 20.5%
浏览 935
已采纳

三足鼎立

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条回答 默认 最新

  • threenewbee 2017-09-30 13:38
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能