P6899 [ICPC 2014 WF] Pachinko

有一个宽度为 $w$ 高度为 $h$ 的方格纸， $ w \times h$ 的格子中，有一些是空的，有一些是洞，有一些是障碍物。从第一行的空的格子中随机选一个放置一个球，向上下左右移动的概率比为 $p_u : p_d : p_l : p_r$（满足 $p_u + p_d + p_l + p_r = 100$），不能移动到有障碍物的格子上。对于每个洞，输出落入该洞的概率。$w \le 20, h \le 10000$。保证第一行没有洞。

无

无

Time limit: 5000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2014