T590313 Bloxorz

**时间限制：** 1.0 秒 **空间限制：** 512 MB

Bloxorz 是一款风靡全球的益智游戏，以其独特的方块操控和复杂的关卡设计而著称。在这个游戏中，玩家需要使用键盘方向键来控制方块的移动，使其到达指定的终点。  具体的游戏规则如下：给定一个平面网格区域，每一格为空地，地面或玻璃。在地面上放置着一块 $1\times 1\times 2$ 的长方体木块，可以**竖放**在**一格地面**上，或**平放**在**相邻的两格地面、或相邻的两格玻璃、或相邻的一格地面和一格玻璃上**。每次操作可以选择四个方向中的一个，将木块向该方向滚动 $90\degree$。游戏的目标是以最少的移动次数将盒子**竖放**在唯一的目标地砖上。初始位置和目标位置的区域类型均为地面，而非玻璃或者空地。 给定一个 $n\times m$ 的平面网格，其中 `#` 表示空地，`.` 表示地面，`E` 表示玻璃，`X` 表示初始位置，`O` 表示目标位置，求达成游戏目标的最小操作数。

从标准输入读入数据。 **本题包含多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 输入的第一行包含两个正整数 $n,m$，表示平面网格的大小。 输入的第 $i+1~(1\le i\le n)$ 行包含一个长度为 $m$ 的仅由 `#`、`.`、`E`、`X`、`O` 组成的字符串，描述给定的游戏局面，具体含义如【题目描述】中所示。

输出到标准输出。 对于每组测试数据： 输出一行一个整数表示到达成游戏目标的最小操作数。特别地，若游戏目标无法达成，则输出 $-1$。

### 子任务 对于所有测试数据，保证 $1\le T\le 5,~3\le n,m\le 500$，保证每个游戏局面都有恰好一个 `O` 与恰好一个 `X` 或相邻的两个 `X`。保证给定的游戏局面中的第一行、第一列、最后一行、最后一列均为 `#`。 **本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。** | 子任务编号 | 分值 | $n,m\le$ | |:---:|:---:| :---: | | 1 | 30 | $20$ | | 2 | 20 | $50$ | | 3 | 20 | $300$ | | 4 | 30 | $500$ |