A169716.风向通道

$Sherry$ 来到了一座风向迷宫。迷宫可以看成一个 $n$ 行 $m$ 列的网格，每个格子中有一个方向字符：

• U 表示向上；
• D 表示向下；
• L 表示向左；
• R 表示向右。

$Sherry$ 每次可以从当前格子移动到上下左右相邻的一个格子中。

如果移动方向与当前格子中的方向相同，那么这一步不需要消耗能量；否则，这一步需要消耗 $1$ 点能量。

现在给定起点和终点，请你求出从起点到终点需要消耗的最少能量。

第一行输入两个整数 $n,m$，表示迷宫的行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示每个格子的方向。

最后一行输入四个整数 $s_x,s_y,t_x,t_y$，分别表示起点和终点的位置。

输出一个整数，表示从起点到终点需要消耗的最少能量。

数据范围

$1\le n,m\le 1000$

$1\le n\times m\le 10^6$

$1\le s_x,t_x\le n$

$1\le s_y,t_y\le m$

保证每个格子中的字符均为 U、D、L、R 之一。