#P17702. [ICPC 2019 Nanjing R] Holes
[ICPC 2019 Nanjing R] Holes
题目描述
给定一个 的棋盘,行和列均从 到 编号。帅气少年 RDC 在指定位置打了若干个洞,其中第 个洞位于 。
RDC 还养了一只名叫 PRD 的宠物猪排骨龙。现在,PRD 喝醉了,被留在了棋盘的格子 上。它将会随机行走,每秒以等概率移动到一个相邻的格子。这里两个格子相邻当且仅当它们共享一条公共边。当 PRD 到达一个被打洞的格子时,它会掉进洞里并开始睡觉。
现在,RDC 想知道对于每个洞,他的宠物最终停留在该洞的期望耗时。
输入格式
第一行包含一个整数 (),表示测试数据的组数。
对于每组测试数据,第一行包含两个整数 和 (),表示给定棋盘的大小和洞的数量。接下来 行,第 行包含两个整数 和 (),表示第 个洞的位置。每组测试数据的最后一行包含两个整数 和 (),意义如上所述。
我们保证 PRD 初始时不在任何一个洞上,且所有给定的洞互不相同。我们还保证至多只有一组测试数据满足 。
输出格式
对于每组测试数据,在一行内按顺序输出到达每个洞的期望耗时(以秒计)。
更确切地说,如果一个洞是可达的,且期望耗时的既约分数为 ,你应当输出最小的非负整数 使得 。你可以放心地假设在所有测试数据中这样的 总是存在。如果一个洞是不可达的,则在对应的位置输出 GG。
2
3 3
1 1
1 2
2 1
2 2
5 3
5 3
4 1
3 2
4 5
GG 4 4
669185882 381533358 341349117
提示
翻译由 DeepSeek V4 Pro 完成