8568: Patrick's Parabox

Patrick's Parabox是一款类似Sokoban的游戏。索科班拼图是一条腰带，每个牢房都是一堵墙或一层地板。在一些不同的地板单元中有几个盒子和一个播放器，它们不能移动到墙壁单元或重合。您可以控制播放器在四个方向之一上移动，左，右，上和下。当玩家触摸盒子时，它可以推动盒子。目标是将所有框移动到某些目标单元格。

请仔细阅读以下规则。它们可能与通常的规则

不同 在这个问题中，只有一个盒子，盒子就是网格本身。这意味着如果玩家移出网格，它可能会被“传送”到盒子附近的一个单元格;如果玩家移动到盒子，它可能会被“传送”到网格边界上的一个单元格。此外，玩家还有一个目标单元格。玩家也需要在最后移动到目标单元格。

给定一个谜题，你需要找到推动盒子的最短时间，以便盒子和玩家分别移动到目标单元格。

以下是详细和正式的规则。

考虑一个$n\times m$网 格。表示(i，j)作为 中的单元格$我$-第一行和$j$-列。行已编号$1$,$2$,$\cdots$,$n$从上到下，列已编号$1$,$2$,$\cdots$,$m$从左到右。

将 W、S、A 和 D 表示为控制命令，这意味着分别向上、向下、向左和向右移动。

定义vW=(−1,0) vs=(1,0) vA=(0,−1)vD=(0,1).

定义
wW=(n,⌈m/2⌉), wS=(1,⌈2/m⌉)wA=(⌈2/n⌉,m)wA=(⌈2n⌉,m), wD=(⌈n/2⌉,1)wD=(⌈n/2⌉,1).

在每个操作中，您可以选择其中一个控制命令$c$，W、S、A 和 D 之一。$p$作为包含播放器的单元格，并且$b$作为操作前包含框的单元格：

• 如果p+vc=b和b+vc是一个地板单元，玩家移动到p+vc并将框移动到b+vc.只有这种情况才会被计入答案中。
• 如果p+vc是一个壁细胞，什么也没发生。
• 如果p+vc是地板单元，并且p+vc≠b，播放器移动到p+vc
• 如果p+vc=b和b+vc在网格之外，没有任何反应。
• 如果p+vc=b,b+vc是一个壁细胞，什么也没发生。
• 如果p+vc=b,b+vc是壁细胞和wcw_cwc是一个地板单元，玩家移动到wcw_cwc.
• 如果p+vc在网格之外，并且b+vc是一个壁细胞，什么也没发生。
• 如果p+vc在网格之外，并且b+vc在网格之外，没有任何反应。
• 如果p+vc在网格之外，并且b+vc是一个地板单元，玩家移动到b+vc.

有多个测试用例。第一行输入包含一个整数TT(1\le T\le 10^51≤T≤10)5)，测试用例的数量。对于每个测试用例:第一行包含两个整数nn和mm(2\ len2≤n, m\le10^5m≤10)5)，抛物面的大小。下面的nn行包含一个长度为mm的字符串。每个字符都是“#”，“”。"， " p "， " b "， " = "和" - "。“#”表示墙单元格，“p”表示球员所在的楼层单元格，“b”表示盒子在的楼层单元格，“=”表示球员所在的目标楼层单元格，“-”表示盒子所在的目标楼层单元格，以及“”表示另一层单元格。它保证每一个" p "， " b "， " = "， " - "只出现一次。它保证所有测试用例的nmmm之和不超过4\乘以10^54×105

对于每个测试用例:
如果无法移动方块和玩家到目标单元格，则输出-1−1。否则，输出一个整数——推箱子的最小次数。

3
9 9
#########
#####..-#
#..=##.##
#.p.##.##
....##.##
#...b..##
#...##.##
#....####
####.####
9 9
#########
#.......#
#.#####.#
#.#=....#
..#....-#
###.p.#.#
#.....#b#
#.....#.#
####.####
9 9
####.####
#....####
#.####.##
#.......#
#.......#
###.#####
#=.b#..##
#-..p..##
#########

7
4
19