P13436 [GCJ 2009 #1B] Square Math

假设我们有一个边长为 $W$ 的正方形网格，因此总共有 $W^2$ 个格子。我们进一步规定，每个格子可以填入以下内容之一： - 一个 $0$ 到 $9$ 的数字； - 加号（+）； - 减号（-）。 如果我们再加上如下约束：任意两个数字不能在水平方向或竖直方向相邻，任意两个运算符（+ 或 -）也不能在水平方向或竖直方向相邻，那么这样的正方形就称为一个“算术方格”。 Square Math 是这样一种谜题：给定一个算术方格，我们可以从任意一个数字格子出发，每次可以水平或竖直移动一格，最终在一个数字格子结束。我们按照经过的格子的内容，拼接成一个数学表达式并计算其值。例如： ``` 2+3 +4- 1+0 ``` 上面是一个 $W=3$ 的合法算术方格。如果我们从“2”出发，向右水平移动，再向下垂直移动，就得到“2+4”，其值为 $6$。如果我们再向右水平移动，再向上垂直移动，就得到“2+4-3”，其值为 $3$。 在 Square Math 中，对同一个格子的使用次数没有限制。也就是说，可以从某个格子移动到相邻格，再返回原格，这样的路径是允许的。给定一个算术方格和若干个查询值，请你为每个查询值找到一个 Square Math 路径，使得对应的表达式计算结果等于该值。

第一行是一个整数 $T$，表示测试用例数。接下来有 $T$ 组测试数据。每组测试数据的第一行包含两个整数 $W$ 和 $Q$。接下来 $W$ 行，每行 $W$ 个字符，表示算术方格。保证所有输入的算术方格都是合法的。再接下来一行，包含 $Q$ 个用空格分隔的整数，表示需要通过 Square Math 得到的目标值（查询）。保证每个目标值至少有一种合法的 Square Math 表达式可以实现。

对于每组测试数据，先输出一行 "Case #$X$:"，其中 $X$ 是测试编号（从 1 开始）。然后对于本组中的每个查询，输出一行对应的 Square Math 表达式。 如果有多种可能的表达式，输出最短的那一个。如果仍有多个最短表达式，输出字典序最小的那个。注意，'+' 的字典序小于 '-'。

**限制条件** - $1 \leq T \leq 60$ **小数据集** - 时间限制：3 秒 - $2 \leq W \leq 10$ - $1 \leq Q \leq 20$ - $1 \leq$ 每个查询 $\leq 50$ **大数据集** - 时间限制：12 秒 - $2 \leq W \leq 20$ - $1 \leq Q \leq 50$ - $1 \leq$ 每个查询 $\leq 250$ 翻译由 ChatGPT-4.1 完成。