P16854 [GKS 2021 #E] Birthday Cake
题目描述
给定一个 $R$ 行 $C$ 列的网格，代表一块生日蛋糕。
行从上到下编号为 $1$ 到 $R$，列从左到右编号为 $1$ 到 $C$。网格中的每个单元格都是 $1 \times 1$ 的正方形。
你发现蛋糕中最美味的部分形成了一个单一的实心矩形；也就是说，该矩形内部的所有单元格都是美味的，而矩形外部的所有单元格都不是美味的。
你有一把足够长的刀，可以进行长度不超过 $K$ 的直线切割。
我们希望进行一系列切割，将每个美味单元格单独分离出来，以便在上面放蜡烛，享受生日聚会。
为了单独分离每个美味单元格，它们必须与任何其他单元格断开连接。如果一个单元格在上下左右四个方向都没有与其他单元格相连，则称该单元格是断开的。
切割是一条有向线段，如果满足以下条件，则是有效的：
- 切割沿着网格的行与列之间的水平或垂直直线进行。
- 切割的长度不得超过 $K$。
- 切割的起点和终点必须是格点（即单元格的角点）。此外，起点必须是已经暴露的，即位于网格的四个边之一或之前的某条切割上。
- 切割不得穿过任何其他暴露点。它可以接触暴露点，但如果接触，则必须恰好在此结束。
假设 $K = 4$。下面给出了五个有效切割的示例。
:::align{center}
:::
以下是四个无效切割的示例。
:::align{center}
:::
- 第一张图中，切割太长（超过 $4$）。
- 第二张图中，切割从未暴露的点开始（既不是网格的四个边也不是之前的切割）。
- 第三张图中，切割穿过了暴露点，它应该在长度为 $2$ 触及暴露点时停止。
- 第四张图无效的原因与第三张图相同。
我们需要找出分离所有美味单元格所需的最少切割次数。
输入格式
输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。
每个测试用例的第一行包含三个整数 $R$、$C$ 和 $K$。
下一行包含四个整数 $r_1$、$c_1$、$r_2$、$c_2$，分别表示美味矩形的左上角和右下角单元格。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最少切割次数。
说明/提示
在样例中，最少切割次数为 $5$。一种可能的切割序列如下：
:::align{center}
:::
在附加样例中，最少切割次数为 $3$。一种可能的切割序列如下：
:::align{center}
:::
### 限制条件
$1 \le T \le 100$。
$1 \le r_1 \le r_2 \le R$。
$1 \le c_1 \le c_2 \le C$。
**测试集 1**
$1 \le R, C \le 100$。
$K = 1$。
**测试集 2**
$1 \le R, C \le 10^5$。
$1 \le K \le 10^5$。
翻译由 DeepSeek V4 Pro 完成