P13258 [GCJ 2014 #2] Don't Break The Nile
题目描述
外星人已经降临地球。他们对地球上的河流感到非常着迷，因为他们的母星上完全没有流动的水。如今，他们想在地球的某些河流中建造外星建筑。
你的任务是确保这些建筑不会过度阻碍河流的流动，否则将会造成严重后果。特别地，你需要判断在建筑布置完成之后，该河流仍然能够承受的**最大水流量**。
这些外星人倾向于在**笔直且宽度一致**的河道段落上建造建筑。因此，你决定将河流建模为一个**矩形网格**，网格中的每个单元格都有整数坐标 $(X, Y)$，其中 $0 \leq X < W$ 且 $0 \leq Y < H$。每个单元格最多只能承载 $1$ 单位的水流，水只能在边相邻的格子之间流动。
所有在河流**南侧**（即 $y$ 坐标为 $0$）的格子默认拥有 $1$ 单位的入流量。
建筑均为矩形，且与网格对齐。位于建筑下方的单元格将无法承载任何水流。给定这些限制条件，请你计算出**最多有多少单位的水流可以到达河流的北侧**（即 $y$ 坐标为 $H - 1$ 的格子）。
输入格式
输入的第一行是测试用例数量 $T$。接下来是 $T$ 个测试用例。
每个测试用例第一行包含三个整数：河流的宽度 $W$，高度 $H$，以及要在河流中建造的建筑数量 $B$。
接下来的 $B$ 行中，每行包含四个整数：$X_0$、$Y_0$、$X_1$ 和 $Y_1$，表示建筑的左下角坐标为 $(X_0, Y_0)$，右上角坐标为 $(X_1, Y_1)$。
建筑之间不会重叠，但可以共边相接。
输出格式
对于每个测试用例，输出一行，格式为 `"Case #x: m"`，其中 $x$ 是测试用例编号（从 1 开始），$m$ 是该河流中最多可以通过的水流量。
说明/提示
**样例解释**
以下是两个样例中河流与建筑布置的可视化图示：
## 限制条件
- $1 \leq T \leq 100$
- $0 \leq X_0 \leq X_1 < W$
- $0 \leq Y_0 \leq Y_1 < H$
### Small 数据集（10 分）
- 时间限制：~~60~~ 3 秒
- $3 \leq W \leq 100$
- $3 \leq H \leq 500$
- $0 \leq B \leq 10$
### Large 数据集（20 分）
- 时间限制：~~120~~ 5 秒
- $3 \leq W \leq 1000$
- $3 \leq H \leq 10^8$
- $0 \leq B \leq 1000$
翻译由 ChatGPT-4o 完成