Maze Statistics

Jim is running a unique carnival attraction. Customers must enter a building and find their way through a randomly generated maze to win a prize. The maze configuration can be different for each customer; he uses a computer program to build his mazes out of a square room with various retractable barriers. The room is divided into an mxn grid of squares, and each square can be either empty or a barrier. The entrance to the room is at the upper left and the exit is at the lower right. The computer program is fairly simple: it creates a maze where each square has a certain inde- pendent 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 m × n 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. Sample Input 2 22 0.5 0.5 0.5 0.5 55 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 Sample Output 0.000000 0.333333 0.333333 0.000000 0.000000 0.158575 0.158575 0.290498 0.290498

2/2 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