问题描述

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

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

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

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

输入格式

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

后面 $m$ 行, 每行四个正整数 $x_{i1}, y_{i1}, x_{i2}, y_{i2}$ 表示第 $i$ 个传送门连接的两个格子坐标。

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

2 1
1 1 2 2

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_{i1}, y_{i1}, x_{i2}, y_{i2} \leq n$。

注意：题目未保证一个位置只有一个传送门