10057번 - Pachinko 스페셜 저지다국어

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⁹. 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 ≤ w ≤ 20 and 2 ≤ h ≤ 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⁻⁶.