OI题库

【题目描述】

防御墙是一种保护城市或定居点免遭潜在侵略者袭击的工事。从古至今，人们都在定居点周围修建这些墙。

通常，它们被称为城墙。虽然这样，我们的祖先决定修建长城来保护中原免遭各种游牧部落的入侵。

地图是一个给定的N*M矩形区域。每一个格子是一块空地，一座城市或者一支敌军。长城是一个边沿着格线的简单多边形，围住了所有的城市，将所有的敌军挡在外面。

长城并不容易建造，因此我们必须让长城尽可能短。现在你的任务是计算围住所有城市但不围住任意一支敌军的长城的最短长度。

【输入格式】

输入文件的第一行是一个整数T(1<=T<=50)，代表数据组数。

每组数据有若干行。

数据的第一行有两个正整数H,W(1<=H,W<=8)，代表地图的行数和列数。

接下来H行每行有W个字符，代表相应的格子。'o'代表城市，'.'代表空地，'x'代表敌军。

保证至少有一座城市。

【输出格式】

对每组数据，输出一行"Case #X: Y"，其中X是数据编号（从1开始），Y是长城的最短长度（如果无法建造，输出-1）。

【样例输入】

3

3 3

.o.

.x.

o.o

4 4

....

.ox.

.xo.

....

5 5

.ooo.

.x...

..xoo

x.xoo

.ox.x

【样例输出】

Case #1: 14

Case #2: -1

Case #3: 28

【提示】

一个简单多边形是平面上一系列线段围成的封闭区域，这些线段之间除了相邻边之外没有公共点。

样例的第一组数据的解见图1.

样例的第二组数据没有解，因为无论如何修建长城，它的非相邻边总会相交。

【来源】

UVa1501 Construct the Great Wall