BOBALLS - Bouncing Balls
Consider a grid having NxM squares. The top left square is (0, 0) and the bottom right is (N-1, M-1). Each square in the grid is either occupied by a platform or has a number written on it. Two balls are released from the top of the grid (from locations (0, Y1) and (0, Y2), 0 <= Y1, Y2 < M). Each ball falls down vertically, unless either it falls down the bottom row, or encounters a platform beneath. When the ball encounters a platform beneath, it rolls either to the left or to the right, each with an equal probability. The score obtained by a ball is the sum of the numbers on the squares that it passes (including the starting square). However, if both the balls pass over the same square, points corresponding to that square are obtained only once, and not twice. Your goal is to choose Y1 and Y2 such that the expected score obtained by the two balls is maximized. For example, consider the grid below: (P represents a platform)
N = 6, M = 6 112214 211243 30PPP2 423378 1P9753 220102
Here, dropping a ball from position (0, 3) could result in one of the following three scores:
- 2 + 2 + 1 + 1 + 0 + 2 + 4 + 1 + 2 = 15
- 2 + 2 + 1 + 1 + 0 + 2 + 3 + 9 + 0 = 20
- 2 + 2 + 4 + 3 + 2 + 8 + 3 + 2 = 26
The expected score is (considering only 1 ball):
1/2*(1/2*(15) + 1/2*(20)) + 1/2*(26)
Input
The first line contains the number of test cases.
The first line for each test case consists of N and M.
Lines 2..N+1 for each test case consist of M characters each. Each character is either a digit from 0 to 9, or the letter 'P'.
Output
The maximum expected score accurate to 4 decimal places.
Example
Input: 4 5 5 53214 53214 53214 54214 53214 5 5 00000 0P0P0 00000 01P20 00000 5 5 09090 0P0P0 00000 01P20 00000 6 6 112214 211243 30PPP2 423378 1P9753 220102 Output: 45.0000 2.2500 19.3125 35.5000
Constraints
Dataset 1: 1 <= number of test cases <= 100
3 <= N, M <= 100
All possible paths from the top will eventually lead to the ball falling to the bottom. There will be no "rebounds" possible. If there is a 'P' on square (x, y), there will not be a 'P' on squares (x-1, y-1) or (x-1, y+1) or (x+1, y-1) or (x+1, y+1). Also, platforms will not occur on the boundaries of the grid. Thus, the X coordinate of a platform will never be 0 or N-1, and the Y coordinate will never be 0 or M-1. The test case was generated to guarantee that any answer with absolute error in 1e-9 will got accepted. Time limit: 7s
Added by: | Race with time |
Date: | 2009-02-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Code Craft 09 |