P3440.第2题-故障机器人
题目内容
给定一张n×m的网格图，每个网格可以是“空地” 或者“障碍”“空地” 用.表示，“障碍”用x表示。
约定从上至下第1行，从左至右第j列的网格表示为(i,j)
此外，一个起点和一个终点被给定，保证起点和终点均为空地。
在起点处，有一个机器人，它想要前往终点。在机器人原本的设定中，假设它当前在(x,y)，则它可以选择向上下左右四个方向移动一格，到达(x,y+1),(x,y−1),(x−1,y)或是(x+1,y)。
当然，机器人在移动的过程中不能经过障碍(在每一步移动中，移动前后所处的网格都需要是空地)，也不能从网格边界离开。
可惜的是，这台机器人因为年代久远，不可避免地发生了机械故障。
故障表现在:
如果它上一步选择了向上或者向下移动，则当前只能选择向左或者向右移动;
如果它上一步选择了向左或者向右移动，则当前只能选择向上或者向下移动。
形式化的，设机器人的行动轨迹按顺序依次是P1.P2...Pk(包含起点和终点)。则不存在两点pi(xi,yi)和pj(xj,yj)同时满足∣i−j∣=2且max(∣xi−xj∣,∣yi−yj∣)=2
请你回答，这台故障的机器人从起点走到终点至少需要几步呢?
当然，障碍的存在使得它有可能永远也无法抵达终点。此时，请输出−1
输入描述
第一行两个正整数n和m。
第二行四个正整数xs′ys′xT′yT(1≤xs′xT≤n,1≤ys′yT≤m)，分别表示起点和终点的坐标。其中，起点的坐标是(xs′ys)，终点的坐标是(xT,yT)。
接下来n 行，每行一个长为m的字符串，表示网格图。
保证给出的所有n×m个字符只会是.(空地)或者X(障碍)，且起点和终点一定是空地。
注意，起点和终点有可能重合。
1≤n,m≤2000
输出描述
输出一行，一个整数，表示机器人从起点出发抵达终点所需的最小步数。
样例1
输入
4 4
1 3 4 3
X...
..XX
..X.
X..X
输出
7
