#P2228. 0x60图论（练习）31：Pushing Boxes（负责人：不干人事的HYY）
0x60图论（练习）31：Pushing Boxes（负责人：不干人事的HYY）
Description
【背景】小鱼参加了一年一度的推箱子大赛
听说谁最快谁完成比赛，谁就能赢得dark奖
作为小鱼的助手，你得帮小鱼争取更高的名次
小鱼：事成之后，我给你1000000000%1块钱
【题意】
比赛是一个n*m的地图
上面有许多障碍，我们用字符"#"表示，其他地方都是空地，用字符"."表示
我们会给出小鱼的起点坐标，箱子的坐标，终点坐标
你要指挥小鱼走到箱子旁边，把箱子推到终点
推动箱子的方法是:
当且仅当小鱼的坐标与箱子的坐标相邻，小鱼才可以面向箱子、并推着箱子往前行进一格
但是，若箱子背面有障碍时，小鱼不能推动箱子
因为小鱼太矮了，所以它翻不过箱子和障碍物
当然，地图外面围了一圈栅栏，也算障碍
现在你的任务是:找出一种方案，使箱子移动步数最少
这个方案的表达方式是一串字符
可能包含 N,S,W,E 这4个字母，它们表示箱子的移动（即上下左右）
若有多种方案可以推到终点，选择步数最少且按照N、S、W、E的顺序优先选择箱子的移动方向的方案
【输入格式】
第一行两个正整数n，m，表示地图大小
然后n行每行m个字符，表示地图
然后按顺序给出小鱼初始坐标，箱子坐标，终点坐标
【输出格式】
若无法将箱子推到终点，请输出-1
否则输出一串字符（按题意要求）
【样例输入1】
10 10
.........#
#######..#
#######.##
#######.##
#######.##
#######.##
#####...##
#####.#.##
#####...##
##########
1 2 8 8 1 1
【样例输出1】