思路

• 状态设计：由于两角色始终同坐标，状态为 $(r,c,h_1,h_2)$，其中 $h_1,h_2$ 分别为当前两人的血量（均在 $1\ldots 20$）。

• 转移规则：

  • 尝试四方向，共 $4$ 个方向。
  • 若两图下一格皆为障碍，则跳过。
  • 若仅一侧为障碍，则对应方需要 $h>1$ 才能前进，并使该方血量减 $1$。
  • 若两侧为空地，则血量不变。

• 搜索策略：对状态做按层的 BFS。边权均为 $1$，因此首次到达终点的一层即为最短步数所在层。

题目内容

在量子纠缠的平行宇宙中，探险家「艾克斯」和「泽塔」需要同步操控两个镜像角色，穿越地形迥异的双子地图。他们的命运通过量子纽带相连——移动必须完全同步，障碍物会消耗血量，唯有协作才能抵达终点。

双地图寻路，两个镜像地图尺寸相同，均为 $N×M$ ($N$行$M$列)，角色固定左上起点 $(0,0)$ ，右下终点 $(N-1,M-1)$ ，起点和终点均为空地。地图中障碍物用 # 表示，空地用 . 表示，两个地图的障碍分布不同。两个地图上的角色必须同步移动：在任一时刻，两者所处的位置相同，所移动的步数相同，且下一步的移动方向一致。移动方向只能是上下、左、右四个方向，不允许斜向移动。

• 如果选择某个方向后，两张地图中对应的下一格均为空地，则两名角色均能正常移动至该格，步数增加 step+1 。

• 如果选择某个方向后，两张地图中对应的下一格均为障碍，则不能沿该方向移动，需另选方向。

• 如果选择某个方向后，一侧的下一格为障碍而另一侧为空地，则进入障碍的一方需扣血 $1$ 点，且其移动前的血量必须大于 $1$ (即扣血后仍大于 $0$ )，否则该移动方向不合法；另一侧进入空地不扣血。若满足条件，两名角色仍然会同时移动，步数增加 step+1。

• 障碍格不会因被进入而被清除，仍然视为障碍(可再次进入并再次扣血)。

角色初始血量分别为 $p、q$ ；到达终点时两者的血量必须均大于 $0$ 。现在需要计算到达终点的最小移动步数，以及两名角色的剩余血量之和。

输入描述

输入包含多组测试数据:

第一行一个整数 $T$ ，表示测试用例组数。

每组测试数据的第一行包含 $4$ 个整数 $N、M、p、q$ ，表示地图的行数和列数 $(5≤N,M≤40)$ 以及两名角色的初始血量 $p、q(1≤p,q≤20)$ 。

随后 $N$ 行，每行 $M$ 个字符，表示地图 $1$ 。

再随后 $N$ 行，每行 $M$ 个字符，表示地图 $2$ 。

注意：起点固定为左上角 $(0,0)$ ，终点固定为右下角 $(N-1,M-1)$ 两处均为空地。保证每组地图都有解，即一定存在可到达终点的路径。

输出描述

对于每组测试数据，输出一行包含两个整数：两名角色到达终点的最小移动步数和到达时两者血量之和。保证输入有解。

当存在多条步数相同的最短路径时，选择使两名角色剩余血量之和最大的方案。若剩余血量之和仍相同，任意选择其中之一输出即可。

样例1

输入

1
5 5 4 3
.####
.####
....#
###.#
#.#..
.####
.####
....#
##...
##...

输出

8 7

样例2

输入

1
5 5 3 3
.###.
.###.
.####
#.###
#..#.
.####
.####
.####
..###
#...

输出

8 4