P13399 [GCJ 2010 #2] Elegant Diamond
题目描述
国王雇佣你为他制作一个优雅的菱形。优雅的菱形是由数字组成的二维图形，关于水平轴和垂直轴对称。例如，以下四个图形是优雅的菱形：
```
2 8 3 7
3 3 8 8 2 2
4 1 4 8 3
3 3
2
```
下面这三个图形是菱形，但不是优雅的：
```
2 1 3
1 1 1 2 1 1
1 1 1 1 3 1 3
2 1 1 1
1 2
```
下面这三个图形不是菱形：
```
1 2 8 8
1 1 222 0
2 00000
```
国王会先给你一个菱形，这个菱形可能不是优雅的。你的任务是通过扩展它、添加数字，使其变成优雅的菱形。由于你不想花太多钱，你希望以尽可能小的代价完成这项工作。
### 定义
大小为 $k$ 的菱形由 $2k-1$ 行数字（0-9）组成，数字之间用单个空格分隔，排列方式如下：
- 第 $i$ 行（$1 \leq i \leq k$）前有 $k-i$ 个空格，接着是 $i$ 个数字，数字之间用单个空格分隔。
- 第 $i$ 行（$k < i < 2k$）前有 $i-k$ 个空格，接着是 $2k-i$ 个数字，数字之间用单个空格分隔。
大小为 $k$ 的优雅菱形是满足以下两个对称性质的菱形：
- 水平对称：设第 $i$ 行有 $c_i$ 个数字，第 $i$ 行第 $j$ 个数字（$j=1$ 表示第一个数字）必须等于第 $c_i+1-j$ 个数字。
- 垂直对称：第 $i$ 行第 $j$ 个数字（$i=1$ 表示第一行）必须等于第 $2k-i$ 行第 $j$ 个数字。
可以通过添加数字来扩展一个大小为 $k$ 的菱形。扩展后的菱形需满足以下条件：
- 扩展结果是一个大小 $\geq k$ 的菱形。
- 原始菱形是扩展结果的一部分。也就是说，存在某个 $X$ 和某个 $Y$，使得对于原始菱形中所有第 $i$ 行第 $j$ 个为数字（非空格）的字符，扩展结果中第 $i+Y$ 行第 $j+X$ 个字符也是数字，且与原始菱形对应位置的数字相同。
扩展菱形的代价等于扩展后菱形中的数字总数减去原始菱形中的数字总数。
输入格式
第一行输入测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据第一行为一个整数 $k$，接下来为一个大小为 $k$ 的菱形。
输出格式
对于每组测试数据，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 为测试编号（从 1 开始），$y$ 为将给定菱形扩展为优雅菱形所需的最小代价。如果菱形已经是优雅的，则 $y=0$。
说明/提示
**样例解释**
共有四组数据。前两组数据本身就是大小为 1 和 2 的优雅菱形，无需扩展，代价为 0。第三组可以扩展为如下优雅菱形：
```
3
1 1
1 2 1
1 1
3
```
有多种扩展方式，但这是代价最小的一种，代价为 5。第四组可以扩展为如下优雅菱形：
```
9
1 1
6 3 6
9 5 5 9
6 3 6
1 1
9
```
……代价为 7。
**数据范围**
- $1 \leq T \leq 100$。
**小数据范围（4 分，测试点 1 - 可见）**
- 时间限制：3 秒。
- $1 \leq k \leq 10$。
**大数据范围（8 分，测试点 2 - 隐藏）**
- 时间限制：6 秒。
- $1 \leq k \leq 51$。
由 ChatGPT 4.1 翻译