题目描述

You have been hired by Addictive Coin Machines to help design the next hit in their line of eye-catching, coin-guzzling, just-one-more-try Pachinko machines for casinos around the world.

Playing a Pachinko machine involves launching balls into a rectangular grid filled with pegs, obstacles, and targets. The ball bounces around the grid until it eventually hits one of the targets. The player earns a certain number of points depending on which target is hit.

The grid pattern for the next Pachinko machine has already been designed, but point values for the targets have not been assigned. These must be set so that like all casino machines, the machine is profitable but not too profitable. Thus it is important to figure out the probability of a ball hitting any particular target. That’s your job!

For simplicity, the grid is modeled as a tall rectangle filled with mostly-open spaces (each represented by ‘.’), impassable obstacles (each represented by ‘X’), and targets (each represented by ‘T’).

A ball is launched randomly with uniform probability into one of the mostly-open spaces on the top row of the grid. From that point on, collisions with pegs cause the ball to randomly bounce up, down, left, or right, with various given probabilities. For simplicity, assume these probabilities are the same for every space in the grid. If the ball bounces into an obstacle or attempts to move off the grid, it won’t actually move from its current space. When the ball moves into a target it is removed from play.

You can safely assume that the average number of spaces visited by a ball before hitting a target will not exceed $10^{9}$. It would not make for a very enjoyable game if the ball just bounces forever!

For each target, calculate the probability that it is the one hit by a launched ball.

输入格式

The input consists of a single test case. The first line contains integers $w$ and $h$, which are the width and height of the Pachinko grid ($1 \leq w \leq 20$ and $2 \leq h \leq 10\, 000$). The next line contains four non-negative integers $u$, $d$, $l$, and $r$, which sum to 100 and are the percentage probabilities of the ball bouncing up, down, left, or right from any open space.

Each of the next $h$ lines contains $w$ characters, each of which is ‘.’, ‘X’, or ‘T’. These lines describe the Pachinko grid. The first line, which describes the top row of the grid, contains at least one ‘.’ and no ‘T’s.

输出格式

Display one line for each ‘T’ in the grid, in order from top to bottom, breaking ties left to right. For each target, display the probability that a launched ball will hit it. Give the answer with an absolute error of at most $10^{-6}$.

题目大意

题目描述

有一个宽度为 $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}$ 即为正确。

3 2
20 20 20 40
X.X
T.T

0.333333333
0.666666667

4 5
12 33 28 27
....
.XX.
....
T..T
XTTX

0.435853889
0.403753221
0.081202502
0.079190387

提示

Time limit: 5000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2014