U485599 小A寻路

>题解：[由cxk_ctrl编写的BFS题解](https://www.luogu.com.cn/article/sx14q5pq) > >若有更多思路欢迎投稿！ 本题数据强度**较高**。 经过小A的奋斗，他打败了地下城的恶魔；但据说在这里的某处埋藏着恶魔的宝藏，因此他打算找到宝藏。

小A来到了恶魔的地下藏宝殿。这里是一个由 $n$ 行和 $m$ 列的方格组成的平面图形；每个方格都有两种形态：`#` 或 `=` 。其中，`#` 代表这一格是墙，不能前进；`=` 代表这一格是道路，可以到达。在可以到达的格子里，可以向上、下、左、右、右上、右下、左上、左下八个方向前进一格（如果前进的目标格没有障碍）。 现在小A想找到恶魔藏在 $x,y$ 格的宝藏；但很不巧，小A是个路痴，所以需要你来帮他设计一个导航程序：如果有一条道路可以通向藏宝点，就帮助他找到宝藏；否则告诉他过不去。 注意：**不**保证所有数据只有 $≤1$ 条可以通向藏宝点的路，但**可以**保证有解的数据只有一项最优解。

$n+3$ 行。 第一行输入 $n$ 和 $m$； 第二行输入起点的行与列； 第三行输入终点的行与列； 接下来 $n$ 行每行输入 $m$ 个字符，即此位置的形态。

一行或若干行。 若无解（例如终点被堵死、中途没有路等情况）输出 `can't` ； 否则每行输出小A应该移动的方案，从他所在的行、列到应该到的行、列；例如：`1,1 to 2,2` 。 在所有方案输出结束后，即小A找到宝藏后，输出 `over`。

$m,n,x,y$ 均在给定的地图范围内。 对于所有数据中的变量，保证其数值 $a$ ：$0＜a≤20$。 ### 重磅提示！！！ - 本题**不**保证地图是正方形； - 本题**保证**起点不与终点重合； - 如果你 WA 但不知道为什么的话，不妨看看你的程序是否优先计算向斜线方向移动，而不是优先计算向直线方向移动。