T827097 巡检路线（patrol）

一台机器人正在车间内测试巡检路线。车间可以表示成一个 $N$ 行 $M$ 列的网格，每个格子由一个字符表示： - `W`：墙，不能进入； - `.`：空地； - `C`：摄像头，不能进入； - `S`：机器人的起点，按空地处理； - `U`、`D`、`L`、`R`：分别向上、下、左、右运送机器人的传送带。 机器人在空地或起点上时，可以主动移动到上、下、左、右相邻的一个格子。每次主动移动计 $1$ 步。进入传送带后，机器人不能自行选择方向，而会被运送到箭头所指的相邻格子；传送不计步数。如果下一个格子仍是传送带，就继续被运送。传送带可能形成环，也可能指向无法进入的格子，此时机器人不能自行离开。 摄像头沿上、下、左、右四个方向监控，视线只会被墙挡住，其他格子均不阻挡视线。机器人不能进入被监控的空地。传送带高于监控区域，机器人在传送带上不会被拍到，但传送带不会阻挡摄像头看向后面的格子。如果起点已被监控，机器人一开始就被发现，不能到达任何空地。 对于地图中的每个 `.` 格子，请求出机器人从起点出发，在不被摄像头发现的情况下到达它所需的最少主动移动步数。如果无法到达，输出 $-1$。

第一行包含一个整数 $T$，表示测试数据组数。 每组数据的第一行包含两个整数 $N,M$。 接下来 $N$ 行，每行包含 $M$ 个字符，描述车间。保证恰有一个 `S`，至少有一个 `.`，并且最外圈全部为 `W`。

对每组数据，按从上到下、每行从左到右的顺序，为每个 `.` 格子输出一行，包含其最少主动移动步数，或者 $-1$。 不同组的输出依次相接，不输出额外的空行。不要为起点、墙、摄像头或传送带输出答案。

### 样例解释 起点在第 $3$ 行第 $3$ 列。第 $2$ 行第 $2$ 列的空地被墙隔开，无法到达。先向右移动，再向上移动，可以用 $2$ 步到达第 $2$ 行第 $4$ 列；向右移动 $1$ 步即可到达第 $3$ 行第 $4$ 列。按题目要求的顺序，依次输出 $-1,2,1$。 ## 样例 2 见 `考生目录/patrol/patrol2.in` 与 `考生目录/patrol/patrol2.ans`。该样例满足测试点 $1\sim6$ 的约束。 ## 样例 3 见 `考生目录/patrol/patrol3.in` 与 `考生目录/patrol/patrol3.ans`。该样例满足测试点 $7\sim12$ 的约束。 ## 样例 4 见 `考生目录/patrol/patrol4.in` 与 `考生目录/patrol/patrol4.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 5 见 `考生目录/patrol/patrol5.in` 与 `考生目录/patrol/patrol5.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 6 见 `考生目录/patrol/patrol6.in` 与 `考生目录/patrol/patrol6.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 数据范围 对于所有数据，保证 $1\le T\le10$，每组数据中 $4\le N,M\le100$，同一输入文件中所有 $N\times M$ 的和不超过 $10^5$。 地图只包含 `W`、`.`、`C`、`S`、`U`、`D`、`L`、`R`。每组数据均满足输入格式中的保证。 | 测试点编号 | 附加限制（每组均满足） | | :--------: | :--------------------- | | $1\sim6$ | 没有摄像头和传送带 | | $7\sim12$ | 没有传送带 | | $13\sim20$ | 无 |