迷宫 ### 问题描述 这天, 小明在玩迷宫游戏。 迷宫为一个 $n \times n$ 的网格图, 小明可以在格子中移动, 左上角为 $(1,1)$, 右 下角 $(n, n)$ 为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 $m$ 个双向传送门可以使用, 传送门可以连接两个任意格子。 假如小明处在格子 $\left(x_{1}, y_{1}\right)$, 同时有一个传送门连接了格子 $\left(x_{1}, y_{1}\right)$ 和 $\left(x_{2}, y_{2}\right)$, 那么小明既可以花费 1 的步数向上下左右四个方向之一走一格 (不能 越过边界), 也可以花费 1 的步数通过传送门走到格子 $\left(x_{2}, y_{2}\right)$ 去。 而对于同一个迷宫, 小明每次进入的初始格子是在这 $n \times n$ 个格子中均匀随 机的 (当然运气好可以直接随机到终点), 他想知道从初始格子走到终点的最短 步数的期望值是多少。 ### 输入格式 输入共 $1+m$ 行, 第一行为两个正整数 $n, m$ 。 后面 $m$ 行, 每行四个正整数 $x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}$ 表示第 $i$ 个传送门连接的两个格 子坐标。 ### 输出格式 输出共一行, 一个浮点数表示答案 (请保留两位小数)。 ### 样例输入 ```text 2 1 1 1 2 2 ``` ### 样例输出 ```text 0.75 ``` ### 样例解释 由于传送门的存在, 从 $(1,1)$ 出发到终点 $(2,2)$ 只需要一步; 而从 $(1,2)$ 和 $(2,1)$ 出发也只需要向下/右走一步; 从 $(2,2)$ 出发需要 0 步。所以步数期望为 $\frac{1+1+1+0}{2 \times 2}=0.75$ ### 评测用例规模与约定 对于 $20 \\%$ 的数据, 保证 $n, m \leq 20$; 对于 $100 \\%$ 的数据, 保证 $n, m \leq 2000 ; x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2} \leq n$ 。