P13255 [GCJ 2014 #1C] Enclosure

本题中，你的任务是在一个 $N \times M$ 的矩形网格上放置尽可能少的石头，以便**围住至少 $K$ 个交叉点**。这个网格由 $N$ 条水平线段和 $M$ 条垂直线段组成，它们的交点构成了交叉点。 某个交叉点被认为是“被围住”的，当且仅当以下两种情况之一成立： 1. 在该点上放置了一个石头； 2. 从该点出发，无法仅沿网格线，经过空交叉点，到达网格边缘上的空交叉点。 例如，要在一个 $4 \times 5$ 的网格中围住 $8$ 个交叉点，至少需要放置 $6$ 个石头。下面展示了一个合法的石头放置方案。被围住的交叉点用 "x" 标记。 

输入的第一行是测试用例的数量 $T$。接下来的 $T$ 行，每行包含三个整数：$N$、$M$ 和 $K$，分别表示网格的行数、列数以及需要被围住的交叉点数量。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是围住至少 $K$ 个交叉点所需的最少石头数。

**样例说明** - 在第一个样例中，需要在 $4 \times 5$ 的网格中围住至少 $8$ 个交叉点，最少需要放置 $6$ 个石头。 - 在第二个样例中，要围住 $11$ 个交叉点，最少需要放置 $8$ 个石头。 ## 限制条件 - $1 \leq T \leq 100$ - $1 \leq N$ - $1 \leq M$ - $1 \leq K \leq N \times M$ ### Small 数据集（15 分） - 时间限制：~~60~~ 3 秒。 - $N \times M \leq 20$ ### Large 数据集（30 分） - 时间限制：~~120~~ 10 秒。 - $N \times M \leq 1000$ 翻译由 ChatGPT-4o 完成