AT_ndpc2026_s 2 枚の扉

你有一个 $N \times N$ 的网格。用 $(i,j)$ 表示第 $i$ 行（自上而下）、第 $j$ 列（自左而右）的单元格。 相邻单元格（共享边）之间的状态由一个字符 $c$ 表示： - 如果 $c =.$，两个单元格之间没有任何阻隔，可以自由通过。 - 如果 $c = D$，有一扇普通门，可以自由通过。 - 如果 $c = A$，有一扇特殊门 $A$，可以自由通过。 - 如果 $c = B$，有一扇特殊门 $B$，可以自由通过。 - 如果 $c = \#$，有一堵墙，无法通过。 网格中恰好有一扇门 $A$ 和一扇门 $B$。 相邻单元格之间的状态由字符串 $S_1, S_2, \dots, S_{N-1}$ 和 $T_1, T_2, \dots, T_N$ 给出： - 对于 $1 \leq i \leq N-1,\ 1 \leq j \leq N$，$(i,j)$ 与 $(i+1,j)$ 之间的状态为 $S_{i,j}$。 - 对于 $1 \leq i \leq N,\ 1 \leq j \leq N-1$，$(i,j)$ 与 $(i,j+1)$ 之间的状态为 $T_{i,j}$。 如果从 $(1,1)$ 出发，仅通过上、下、左、右移动且不经过墙，可以到达 $(N,N)$，则称该网格为**良好状态**。 现在你将封锁部分门（除了 $A$ 和 $B$ 外，不包括它们），使其变得不可通行，使得以下条件成立： - 网格处于良好状态。 - 即使你另外再封锁 $A$ 或 $B$ 中的任意一个，网格仍然处于良好状态。 - 如果你另外同时封锁 $A$ 和 $B$，则网格不再处于良好状态。 问能否满足上述条件？如果可以，求至少要封锁多少扇门。 有 $T$ 组测试数据。请解决每组数据。

输入按如下格式给出： > $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ 每组测试数据格式如下： > $N$ $S_1$ $S_2$ $\vdots$ $S_{N-1}$ $T_1$ $T_2$ $\vdots$ $T_N$

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。 对于每组测试数据，如果能满足条件，输出至少需要封锁的门的数量，否则输出 `-1`。

### 样例解释 1 例如在第一个测试数据中，网格已经满足条件，无需操作。 ### 约束条件 - $1 \leq T \leq 10^5$ - $2 \leq N \leq 40$ - 每个 $S_i$ 是一个长度为 $N$，只包含 `.`, `D`, `A`, `B`, `#` 的字符串 - 每个 $T_i$ 是一个长度为 $N-1$，只包含 `.`, `D`, `A`, `B`, `#` 的字符串 - $A$ 和 $B$ 分别恰好出现一次，在所有 $S_{i,j}$ 和 $T_{i,j}$ 中 - 所有测试数据的 $N^2$ 之和不超过 $2 \times 10^5$ - 所有测试数据的 $N^4$ 之和不超过 $40^4$。 由 ChatGPT 5 翻译