Problem A
Maze Statistics
Input: Standard Input
Output: Standard Output
Time Limit: 10 Seconds
The computer program is fairly simple: it
creates a maze where each square has a certain independent probability of being
a barrier. Of course, the maze must have
a solution, so if the program accidentally creates an unsolvable maze, it
starts over and builds a new one.
Jim wants to know what the wear and tear will
be on each of the barriers. So he'd like
information on how often any specific barrier will be in use in a final
maze. You must help him calculate this
probability.
Input
The first line of input contains the number
of cases (no more than 20). Each case follows in turn.
The first line of each case defines the
dimensions of the grid. It consists of m
(1 <= m <= 5), the number of rows, and n (1 <= n <= 6), the number
of columns. The next m lines consist of
n numbers which give the probability (from 0 to 1) that the program tries
putting a barrier into that square of the grid.
There will always be a non-zero probability
that a generated maze will be solvable.
Output
For each case,
output an mxn grid of numbers giving the probability that each individual
barrier will be used in a valid maze.
Probabilities should have 6 digits after the decimal (though a variance
of 0.000001 from the judge answer is acceptable).
Print a blank line between cases.
|
2 2
2 0.5
0.5 0.5
0.5 5
5 0.3
0.3 0.3 0.3 0.3 0.3
1.0 0.3 1.0 0.3 0.3
1.0 0.3 0.3 0.3 0.3
1.0 0.3 1.0 1.0 0.3 0.3 0.3 0.3 0.3 |
0.000000 0.333333 0.333333 0.000000 0.000000 0.158575
0.158575 0.290498 0.290498 0.169997 1.000000
0.190249 1.000000 0.290498 0.169997 1.000000
0.158575 0.290498 0.290498 0.169997 1.000000
0.158575 1.000000 1.000000 0.169997
0.169997 0.000000 0.000000 0.000000 |
Problemsetter: Derek Kisman, Member of Elite Problemsetters' Panel