P10828 [EC Final 2020] Fillomino

庞教授是庞国的国王。庞国是一个大小为 $n\times m$ 的棋盘。第 $i$ 行第 $j$ 列的格子记作格子 $(i, j)$，其中 $1\le i\le n, 1\le j\le m$。如果两个格子共享一条边，则它们是连通的。这个棋盘是一个**环面**，也就是说，对于所有 $1\le x\le n, 1\le y\le m$，格子 $(1,y)$ 也与 $(n,y)$ 连通，格子 $(x,1)$ 也与 $(x,m)$ 连通。 庞教授有三个儿子。我们称他们为大儿子、二儿子和三儿子。他们每个人都住在庞国的一个格子中。第 $i$ 个儿子住在格子 $(x_i, y_i)$。没有两个儿子住在同一个格子中。庞教授希望将庞国的格子分配给他的儿子们，使得： - 每个格子恰好属于一个儿子。 - 对于所有 $1\le i\le 3$，有 $cnt_i$ 个格子属于第 $i$ 个儿子。 - 对于所有 $1\le i\le 3$，属于第 $i$ 个儿子的格子是连通的。 - 对于所有 $1\le i\le 3$，第 $i$ 个儿子所在的格子必须属于他自己。 请帮助庞教授找到一个可能的解决方案。

第一行包含一个整数 $T$ ($1\leq T\leq 10^5$)，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n, m$ ($3\leq n,m \leq 500$)，用一个空格分隔。 下一行包含三个正整数 $cnt_1,cnt_2,cnt_3$ ($cnt_1+cnt_2+cnt_3 = n m$)，用空格分隔。 接下来的 3 行中的第 $i$ 行包含两个整数 $x_i, y_i$ ($1\le x_i\le n, 1\le y_i\le m$)，用一个空格分隔。 保证 $(x_1,y_1)$、$(x_2, y_2)$、$(x_3, y_3)$ 是不同的。 保证所有测试用例中 $nm$ 的总和不超过 $10^6$。

对于每个测试用例，如果没有解决方案，输出一行 $\texttt{-1}$。否则，输出 $n$ 行。每行应包含 $m$ 个字符。如果格子 $(i, j)$ 属于大儿子，则第 $i$ 行第 $j$ 个字符应为 $\texttt{A}$；如果属于二儿子，则为 $\texttt{B}$；如果属于三儿子，则为 $\texttt{C}$。对于所有 $1\le i\le 3$，格子 $(x_i, y_i)$ 必须属于第 $i$ 个儿子。对于所有 $1\le i\le 3$，属于第 $i$ 个儿子的格子必须是连通的。

（由 ChatGPT 4o 翻译）