← 返回题目列表

AtCoder · ndpc2026_s

S. 两扇门

中文机器翻译题面 查看原题

分数: 8 点

问题陈述

您将获得 N \times N 网格。让 (i,j) 表示中的单元格 i从顶部开始的第行和 j左起第 列。

相邻单元格之间的状态(共享边缘)由字符表示 c:

  • If c = .,小区之间没有任何东西,可以自由通过。
  • If c = D,有门,可以自由通过。
  • If c = A,有一个特殊的门叫 A,就可以自由通过了。
  • If c = B,有一个特殊的门叫 B,就可以自由通过了。
  • If 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) is S_{i,j}.
  • 对于 1 \leq i \leq N, 1 \leq j \leq N-1,之间的状态 (i,j) 和 (i,j+1) is T_{i,j}.

网格称为 状态良好 如果你可以从 (1,1) 并达到 (N,N) 向上、向下、向左或向右移动,而不穿过墙壁。

你会挡住一些门(除了 A 和 B),使其无法通行,从而满足以下条件:

  • 网格状态良好。
  • 即使您另外阻止了其中一个 A or B,网格状态依然良好。
  • 如果您另外阻止这两个 A 和 B,网格不再处于良好状态。

是否可以满足这些条件?如果可能的话,找出您需要阻挡的最少门数。

你被给予 T 测试用例。解决它们中的每一个。

约束

  • 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

输入

输入由标准输入给出,格式如下:

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

6
2
.A
.
B
2
.A
#
B
3
#D.
#BD
.A
.#
..
4
DDBD
..#D
#D.D
#DD
#DD
.A.
#.#
4
D.#D
DD#.
D.B.
#D.
.#D
...
.DA
9
DDD.D#DDD
DDDADDDDD
DD.DDDDDD
DDDD#.DDD
DD#DDDD.#
DDDDD#.#D
DD.#..DDD
DDDDD#D.D
DDD...DD
D#.D#D#D
D#DD#D.#
DDD#DD##
BDDD.D#D
DD#DDDDD
DDDDD#DD
DDD#DDDD
##DDD.#D

示例输出 1

0
-1
0
3
-1
7

例如,在第一个测试用例中,条件已经满足。