CF1196E Connected Component on a Chessboard

给定两个整数 $b$ 和 $w$。你有一个大小为 $10^9 \times 10^9$ 的国际象棋棋盘，左上角的格子为 $(1, 1)$，且该格子被涂成白色。 你的任务是在这个棋盘上找到一个连通块，该连通块恰好包含 $b$ 个黑色格子和 $w$ 个白色格子。两个格子如果有公共边，则称它们是连通的（即对于格子 $(x, y)$，最多有四个相邻连通格子：$(x-1, y)$、$(x+1, y)$、$(x, y-1)$、$(x, y+1)$）。如果对于该集合中的任意两个格子 $C_1$ 和 $C_2$，存在一系列格子 $c_1, c_2, \ldots, c_k$，使得 $c_1 = C_1$，$c_k = C_2$，且从 $1$ 到 $k$ 的所有 $c_i$ 都属于该集合，并且对于每个 $i \in [1, k-1]$，$c_i$ 和 $c_{i+1}$ 是连通的，则称该集合为一个连通块。 显然，有时可能无法找到这样的连通块。如果无法找到，输出 "NO"。否则，输出 "YES" 并给出任意一个满足条件的连通块。 你需要回答 $q$ 个独立的询问。

输入的第一行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示询问的数量。接下来有 $q$ 行，每行包含两个整数 $b$ 和 $w$（$1 \leq b, w \leq 10^5$），分别表示所需的黑色格子数和白色格子数。 保证所有询问中所需格子的总数不超过 $2 \times 10^5$（即 $\sum w + \sum b \leq 2 \times 10^5$）。

对于每个询问，输出对应的答案。 如果无法找到满足条件的连通块，第一行输出 "NO"。 否则，第一行输出 "YES"。接下来的 $b + w$ 行，每行输出一个格子的坐标，表示该连通块中的一个格子，顺序任意。你输出的连通块中必须恰好有 $b$ 个黑色格子和 $w$ 个白色格子，且该连通块是连通的。 如果有多种答案，可以输出任意一种。所有坐标必须在 $[1, 10^9]$ 的范围内。

由 ChatGPT 4.1 翻译