给一个 \(n \times m\) 的网格，每个格子对应一个坐标 \((a, b)\) 。如果存在一个各自的坐标为 \((c, d)\) 且满足 \(|a - c| + |b - d| = 1\) ，则称 \((a, b)\) 与 \((c, d)\) 相邻。
给出 \(k + 1\) 个点，初始坐标分别为 \((x_0, y_0), (x_1, y_1), \cdots, (x_k, y_k)\) 。每一秒，每个点可以任意移动一步。其中 \(0\) 号点的初始坐标为 \((x_0, y_0)\) 。
问是否可能，在每一秒的结束时刻， \(0\) 号点永远不与其他 \(k\) 个点相遇。
先讨论一个一维两点的经典问题，每个点每秒可以移动一个单位。已知点 \(x_0\) ，则另一点 \(x\) 若满足 \(x - x_0 \equiv 1 (\mod 2)\) 。这两个点在每秒末不会相遇。
- 证明：\(x\) 和 \(x_0\) 的点在每秒末永远满足 \(x - x_0 \equiv 1 (\mod 2)\) 。于是他们的距离为 \(|1 + 2 \cdot t|\) ，最小为 \(1\) 。qed。
- 推论：已知点 \(x_0\) ，则另一点 \(x\) 若满足 \(x - x_0 \equiv 0 (\mod 2)\) ，则这两个点在有限空间内可以相遇。
大多数问题可以由低维推广到高维，几乎所有问题可以由一维推广到二维，证略。
- 二维的路径长度由每个一维的路径长度相加得到。
于是已有点 \((x_0, y_0)\) ，存在点 \((x, y)\) 满足
\[(x - x_0) + (y - y_0) \equiv 0 (\mod 2)
\]
则 \((x_0, y_0)\) 在某秒末会与该点相遇。
于是 \(check\) 所有 \(i \in [1, k], (x_i, y_i)\) 与 \((x_0, y_0)\) 的关系，若满足上式则可以相遇。否则不能。
此题的 \(n, m\) 无用，只给了空间有限的信息。
view
#include <bits/stdc++.h>
void solve() {
int n, m, k; std::cin >> n >> m >> k;
int sx, sy; std::cin >> sx >> sy;
bool bad = 0;
for (int i = 1; i <= k; i++) {
int x, y; std::cin >> x >> y;
bad |= ((sx - x) + (sy - y)) % 2 == 0;
}
std::cout << (bad ? "NO" : "YES") << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}