CF2199G Jammer

在一个大小为 $n \times m$ 的场地上，有一个机器人初始位于点 $(0, 0)$，它的目标是到达点 $(n, m)$。机器人的每一步只能向右或向上移动一格。也就是说，若当前在 $(i, j)$，下一步可以到 $(i + 1, j)$ 或 $(i, j + 1)$。 你并不知道机器人的具体行进路径，但你需要对其实施拦截。为此，你有一个干扰器，其作用范围为 $r$，你可以将其放置在任何整数点 $(x, y)$ 处（$0 \le x \le n$，$0 \le y \le m$）。 如果机器人在移动的某一时刻，距离干扰器不超过 $r$，即存在路径上的某点 $(i, j)$ 满足 $\sqrt{(i - x)^2 + (j - y)^2} \le r$，则认为机器人被拦截。 但是有一个问题：如果干扰器放得离起点 $(0, 0)$ 或终点 $(n, m)$ 太近，会被发现，你的计划就会暴露。因此，你需要将干扰器放在既不会覆盖起点 $(0, 0)$ 也不会覆盖终点 $(n, m)$ 的位置（即与这两个点的距离都必须严格大于 $r$）。 请计算有多少个合适的位置可以放置干扰器。一个位置如果不离起点和终点太近，并且能够确保无论机器人选择何种路线都能够被拦截，则视为合适的位置。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例，只有一行，包含三个整数 $n$、$m$ 和 $r$（$n, m \ge 1$；$n \cdot m \le 10^9$；$1 \le r \le n + m$），分别表示场地大小和干扰器的作用范围。

对于每一个测试用例，输出一个整数，表示有多少个可以放置干扰器的合适点。

第二个测试用例中的一种可以放置干扰器的位置在题目描述的图片中进行了说明。 由 ChatGPT 5 翻译