P13219 [GCJ 2015 #1B] Noisy Neighbors

你是一名房东，拥有一栋由 $R \times C$ 个公寓组成的大楼，每个公寓是一个单位正方形单元格，四面都有墙。你打算将其中 $N$ 个公寓出租，每个公寓恰好住一名租客，其余公寓保持空置。不幸的是，所有潜在租客都很吵，因此每当有两个被占用的公寓共享一面墙（仅限于共享墙，而不是仅仅是角），大楼的“不愉快值”就会增加 $1$。例如，在一个 $2 \times 2$ 的大楼中，如果每个公寓都被占用，则有四面墙被相邻租客共享，因此大楼的“不愉快值”为 $4$。 如果你以最优方式安排这 $N$ 名租客入住，最小的不愉快值是多少？

输入的第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含三个用空格分隔的整数：$R$、$C$ 和 $N$。

对于每个测试用例，输出一行，格式为 “Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是该大楼可能的最小不愉快值。

**样例解释** 在第 1 个样例中，每个房间都被租客占据，所有 7 面内部墙都有租客在两侧。 在第 2 个样例中，有多种方式可以安排两名租客，使他们不共享墙。其中一种方式如下图所示。 在第 3 个样例中，最优策略是将 8 名租客安排成一个环，中间的公寓空着。 下图展示了样例 1-3 的示意图。每一面红色的墙都会增加一分不愉快值。  **样例说明** - $1 \leq T \leq 1000$。 - $0 \leq N \leq R \times C$。 **小数据集（12 分）** - 时间限制：~~240~~ 5 秒。 - $1 \leq R \times C \leq 16$。 **大数据集（15 分）** - 时间限制：~~480~~ 10 秒。 - $1 \leq R \times C \leq 10000$。 由 ChatGPT 4.1 翻译