5638. Problem C. 鲁星救援 (safe.c/cpp/pas)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 在遥远的 Lu3KO5 星球上，鬼才同学被阴险狡猾的 大兵徐DD 囚禁在一座防御严密的地下堡垒中。这座堡垒是一片巨大的迷宫，由$n \times m$的格子组成，每个格子对应迷宫中的一个位置。鬼才同学被困在$(s_x, s_y)$，而堡垒的出口位于$(t_x, t_y)$。 鬼才同学原本计划通过徐DD为他偷偷挖好的地道$(p_x, p_y)$逃走，但 大兵徐DD 早就猜到了这一步，毁掉了地道并设置了重重障碍，使得整个迷宫危机四伏。在这座堡垒中，任何人只能上下左右移动一格，而障碍物则无法通过。 然而，事情出现了转机！Luke 获得了堡垒的钥匙，并且得知了鬼才同学即将逃跑的消息。他决定迅速赶往救援。然而，Luke 了解到鬼才同学会选择一条最短的路径前往地道，而他不知道的是那条地道已经被摧毁了。为了成功营救鬼才同学，Luke 必须找到一条最短路径，赶到鬼才同学即将经过的路径中的任意一点。 在这场营救行动中，“最短路径”有一个特别的定义：鬼才同学会将他每一步的移动方向编码成一个数字序列，上代表 1，右代表 2，下代表 3，左代表 4。例如，如果鬼才同学的行走方向是$上(1) \rightarrow 左(4) \rightarrow 下(3) \rightarrow 右(2)$，那么路径的编码为$1432$。在所有可能的路径中，编码数字最小的路径才被视为最短路径。 你能帮助 Luke 计算出他最少需要走多少步，才能成功在鬼才同学的行走路径中找到他并完成营救吗？ Input 输入共$n + 1$行。 第一行包含八个正整数$n, m, sx, sy, tx, ty, px, py$。鬼才、家门、地道所处位置互不相同，但不保证家门在家的边缘。 接下来共$n$行，每行$m$个整数，用来描述$XDD$的家的俯视图。其中第$i$行的第$j$个数表示$(i, j)$是否被设置障碍，有用 1 表示，没有用 0 表示。 Output 输出共一行，表示 Luke 最少需要走的步数。 若 鬼才 没有到达地道的可行路径 Luke 没有到达 鬼才 行走的路径中的任意一点的可行路径，则输出 -1。 Examples 【 ## 输入 ## 输入 ```in1 6 6 2 2 5 5 4 4 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 ``` 【 ## 输出 ## 输出 ```out1 7 ``` 【 ```in2 4 4 2 2 3 3 4 3 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ``` 【 ```out2 -1 ``` 【样例输入3】 见下发文件。 【样例输出3】 见下发文件。 Notes 对于$30\%$的数据，$n, m \le 10$。 对于$100\%$的数据，$1 \le sx, tx, px \le n \le 10^3; 1 \le sy, ty, py \le m \le 10^3$。