分数: 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
例如,在第一个测试用例中,条件已经满足。