Pachinko
InterviewTime limit1sMemory limit1024 MB
Given a grid with obstacles and numbered gates, drop a ball in one column to maximize expected winnings as it falls and splits 50/50 at each obstacle.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Probability, Implementation, Matrix
- Solved
- No attempts yet
Problem
Pachinko is a Japanese game played for amusement and prizes, and is similar to pinball. The game is very simple: you shoot small metal balls into the machine and they fall down, bouncing off the obstacles until they fall into a gate. The gate into which your ball falls determines the winnings.
Since you can more or less determine the column into which the ball is dropped (by setting its initial speed and direction), you can influence your win chances. You are to calculate your expected winnings.
We model the pachinko machine as follows: you can drop the ball in any column and it falls down until it either reaches the bottom of the machine (which results in no wins), a gate (indicated by a number 1 to 9, which results in that win) or an obstacle (indicated by an asterisk). If a ball hits an obstacle it proceeds falling in the column to the left or to the right of the obstacle, with 50/50 probability. No two obstacles or gates are adjacent, not even diagonally, and none are located in the leftmost or rightmost column.
Input
On the first line an integer t (1 ≤ t ≤ 100): the number of test cases. Then for each test case:
- One line with two integers h and w (1 ≤ h, w ≤ 100): the height and width of the pachinko machine.
- h lines with w characters describing the pachinko machine. A ‘
.’ denotes an empty space, ‘*’ an obstacle and ‘1’. . . ‘9’ the winning gates.
Output
For each test case:
- One line with the maximal expected winnings with either an absolute or a relative error of at most 10−6.