SP13092 PCPC12F - Snakes and Ladders Again

蛇梯棋是一种起源于印度的古老棋盘游戏，如今已成为世界经典。这款游戏通常有两名或多名玩家参加，棋盘是一个编号网格。棋盘上有一些“梯子”和“蛇”，它们分别连接着两格特定的方格。游戏的目标是将你的棋子从起点（底部方格）移动到终点（顶部方格），梯子可以帮助你上升，而蛇则可能让你下降到更低的位置。游戏的最初版本寓含道德教化意义，代表着人生旅途中的美德（梯子）和恶习（蛇）。如果你的棋子经过掷骰子后停在一个梯子的底部，就可以顺梯而上；若停在蛇的头部，就必须顺蛇而下。我们称这种具有变化的方格为不稳定方格，否则为稳定方格。 这个游戏不依赖技巧，主要是一个竞赛，因此很受小朋友们的欢迎。 在本题中，你需要计算，从棋盘起点（底部方格）到终点（顶部方格）所需的六面骰子投掷次数的期望值。 **游戏规则** 棋盘是一个 \(N \times M\) 的方格网格，其中方格编号从 1 排到 \(N \times M\)。最后一个方格被称为终点方格。每名玩家开始时的棋子位置为 0（即“1”号格旁的虚拟起始空间，即底部方格），这个位置不会变化。棋盘共有 \(N \times M + 1\) 个位置。每回合投掷骰子，按照点数向前移动棋子。如果到达的位置超过顶部方格，则无需移动。如果棋子落到不稳定方格上，则依据蛇或梯子的指示继续移动，直到到达稳定方格为止。你可以假设任何方格都能最终到达一个稳定方格。如果最后到达的位置是顶部方格，游戏即告胜利。

输入包含若干个测试数据。每个测试数据的第一行包含四个整数 \(N, M, S, L\)，分别表示棋盘的行数、列数、蛇的数量和梯子的数量。接下来的 \(S\) 行描述每条蛇，每行有两个整数 \(h\) 和 \(t\)，表示蛇头的位置和蛇尾的位置（\(0 < t < h \leq N \times M\)）。接下来的 \(L\) 行描述每个梯子，每行有两个整数 \(p\) 和 \(q\)，表示梯子底部和顶部的位置（\(0 < p < q < N \times M\)）。 输入以文件结束符标识。 **注意事项！同一方格可能有多条蛇和/或梯子，需按输入中最后出现的为准。**

对于每组测试数据，输出一个数字，表示到达顶部方格所需的骰子投掷次数的期望值。答案保留小数点后三位。 ``` 样例输入 5 10 3 5 16 6 47 26 49 11 1 38 4 14 9 31 40 42 36 44 样例输出 30.198 ``` **本翻译由 AI 自动生成**