这天，小明在玩迷宫游戏。

迷宫为一个 n × n 的网格图，小明可以在格子中移动，左上角为 (1, 1)，右下角 (n, n) 为终点。迷宫中除了可以向上下左右四个方向移动一格以外，还有 m 个双向传送门可以使用，传送门可以连接两个任意格子。

假如小明处在格子 (x1, y1)，同时有一个传送门连接了格子 (x1, y1) 和 (x2, y2)，那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能越过边界)，也可以花费 1 的步数通过传送门走到格子 (x2, y2) 去。

而对于同一个迷宫，小明每次进入的初始格子是在这 n × n 个格子中均匀随机的 (当然运气好可以直接随机到终点)，他想知道从初始格子走到终点的最短步数的期望值是多少。

输入共 1 + m 行，第一行为两个正整数 n, m。

后面 m 行，每行四个正整数 xi1, yi1, xi2, yi2 表示第 i 个传送门连接的两个格子坐标。

输出共一行，一个浮点数表示答案 (请保留两位小数)。

2 1 1 1 2 2

0.75

思路：一看就是搜索题，一开始想的是用深搜，写个循环，依次查找每个点到终点的步数，然后相加求结果，结果说什么killed,很懵逼，然后开始想法剪枝，若搜索过程中，该次搜索的步数大于之前搜索到终点的最小值还大，那就终止，结果还是错。而且用深搜的时候还遇到了map.containsKey错误的情况，原因是map里存了自己定义的类，要重写hashCode()和equals()方法。 然后想到了反向广搜，起始点为终点，然后向其他点走，走到某个点的步数就是该点到终点的步数，注意，这样搜索必然是最短路径，因为BFS有最短路效应。 然后写了一发还是错，又想到了，某个点的传送门不一定是唯一的。 所以最后用Map存一下传送门的位置。终于ac.