P15563 [CCPC 2025 哈尔滨站] 网格避障

给定一个 $n \times m$ 的网格，行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。除最左列 $1$ 与最右列 $m$ 外，每一列至多有一个障碍物；最左列与最右列保证没有障碍物。 你从最左列的任意一个格子出发（行自选），目标是到达最右列的任意一个格子（行自选）。假设你当前在第 $i$ 行第 $j$ 列，每一步你可以选择下列三种操作之一： - 向右：从 $(i,j)$ 走到 $(i,j+1)$； - 向上：从 $(i,j)$ 走到 $(i-1,j)$； - 向下：从 $(i,j)$ 走到 $(i+1,j)$。 不允许向左移动，且任何时刻都不能进入障碍格子,也不能走出网格之外。 共有 $k$ 个障碍（按列号从小到大排序后编号为 $i=0$ 到 $k-1$）。对每个障碍，你必须选择“从上方绕过”或“从下方绕过”。 若第 $i$ 个障碍在列 $c_i$、行 $r_i$： - 选择“从上方绕过”时，你在列 $c_i$ 时的行编号必须始终 $< r_i$； - 选择“从下方绕过”时，你在列 $c_i$ 时的行编号必须始终 $> r_i$。 不同列的选择相互独立，共有 $2^k$ 种方案。 你的任务：对每一种方案，计算在满足该方案所有限制下，从最左列某行到最右列某行的最小步数；若该方案下无可行路径，输出 -1。

本题包含多组测试数据。输入第一行包含一个整数 $T$ ($1 \le T \le 5000$)，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： 第一行包含两个整数 $n, m$ ($1 \leq n \leq 100, 2 \leq m \leq 100$)，分别表示网格的行数与列数。 第二行包含一个整数 $k$ ($0 \leq k \leq \min(m - 2, 10)$)，表示障碍的数量。 接下来 $k$ 行第 $i$ 行包含两个整数 $r_i$, $c_i$ ($1 \le r_i \le n, 1 \le c_i \le m$)，表示在第 $r_i$ 行第 $c_i$ 列有一个障碍。保证 $1 < c_1 < c_2 < \ldots < c_k < m$。 对于所有测试数据，保证 $\sum n \cdot m \leq 5000$，注意对于所有测试数据的 $k$ 之和**并没有约束**。

对于每组测试，输出一行，包含 $2^k$ 个整数，依次表示编号从 $0$ 到 $2^k-1$ 的每一种方案的最小步数。相邻数字之间用一个空格分隔。若某种方案无解，则输出 $-1$。 方案编号说明：每种方案可看作一个长度为 $k$ 的二进制数。二进制数从低位到高位依次对应第 $0, 1, ..., k-1$ 个障碍。某一位为 $0$ 表示从上方绕过该障碍；为 $1$ 表示从下方绕过。 例如：若 $k = 3$，则共有 $2^3 = 8$ 种方案，对应如下 $$ \begin{array}{|c|c|c|} \hline 方案编号 & 二进制表示（低位→高位） & 绕行选择（第\ 0, 第\ 1, 第\ 2\ 障碍） \\ \hline 0 & 000 & 上, 上, 上 \\ \hline 1 & 100 & 下, 上, 上 \\ \hline 2 & 010 & 上, 下, 上 \\ \hline 3 & 110 & 下, 下, 上 \\ \hline 4 & 001 & 上, 上, 下 \\ \hline 5 & 101 & 下, 上, 下 \\ \hline 6 & 011 & 上, 下, 下 \\ \hline 7 & 111 & 下, 下, 下 \\ \hline \end{array} $$ 程序应按照方案编号从小到大的顺序输出每种方案的最小步数。