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$。保证第一行没有洞。

第一行两个整数表示 $w, h$ 。 第二行四个整数表示 $p_u, p_d, p_l, p_r$ 。 接下来有一个 $h$ 行 $w$ 的字符矩阵，其中 `.` 表示空，`X` 表示障碍物，`T` 表示洞。

若干行，每一行一个整数，按照矩阵从上到下，从左到右的顺序，输出每个洞的答案。绝对误差不超过 $10^{-6}$ 即为正确。

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