解题思路

状态设计

这个问题的本质是带状态的最短路/BFS：

• 普通BFS每个格子只需记录是否访问过，但现在要记录“到达该格子的上一动方向”。
• 因为移动方向交替，上一步“竖”（上下）只能现在“横”，上一步“横”只能现在“竖”。

状态变量

题目内容

给定一张$n×m$的网格图，每个网格可以是“空地” 或者“障碍”“空地” 用$.$表示，“障碍”用$x$表示。

约定从上至下第$1$行，从左至右第$j$列的网格表示为$(i,j)$

此外，一个起点和一个终点被给定，保证起点和终点均为空地。

在起点处，有一个机器人，它想要前往终点。在机器人原本的设定中，假设它当前在$(x,y)$，则它可以选择向上下左右四个方向移动一格，到达$(x,y+1),(x,y-1),(x-1,y)$或是$(x+1,y)$。

当然，机器人在移动的过程中不能经过障碍(在每一步移动中，移动前后所处的网格都需要是空地)，也不能从网格边界离开。

可惜的是，这台机器人因为年代久远，不可避免地发生了机械故障。

故障表现在:

如果它上一步选择了向上或者向下移动，则当前只能选择向左或者向右移动;

如果它上一步选择了向左或者向右移动，则当前只能选择向上或者向下移动。

形式化的，设机器人的行动轨迹按顺序依次是$P_1.P_2...P_k$(包含起点和终点)。则不存在两点$p_i(x_i,y_i)$和$p_j(x_j,y_j)$同时满足$|i-j|=2$且$max(|x_i-x_j|,|y_i-y_j|)=2$

请你回答，这台故障的机器人从起点走到终点至少需要几步呢?

当然，障碍的存在使得它有可能永远也无法抵达终点。此时，请输出$-1$

输入描述

第一行两个正整数$n$和$m$。

第二行四个正整数$x_{s'}y_{s'}x_{T'}y_T(1≤x_{s'}x_T≤n,1≤y_{s'}y_T≤m)$，分别表示起点和终点的坐标。其中，起点的坐标是$(x_{s'}y_s)$，终点的坐标是$(x_T,y_T)$。

接下来$n$ 行，每行一个长为$m$的字符串，表示网格图。

保证给出的所有$n×m$个字符只会是$.$(空地)或者$X($障碍)，且起点和终点一定是空地。

注意，起点和终点有可能重合。

$1≤n,m≤2000$

输出描述

输出一行，一个整数，表示机器人从起点出发抵达终点所需的最小步数。

样例1

输入

4 4
1 3 4 3
X...
..XX
..X.
X..X

输出

7