My Faulty Touch Screen
Time limt: 5 seconds
Recently I started playing a mini computer game that is good for killing time. The game board is an m x n grid. Initially the cells are either in black or white. Clicking on a cell flips its color between black and white. The goal of the game is to turn the whole grid black in the shortest time.
I found that the game can be played on my new mobile phone equipped with a touch screen. Unfortunately soon after the touch screen malfunctioned. When I touch a cell on the grid, five other cells are also "touched" so altogether the colors of the six cells are flipped. When one cell is touched, the mobile phone would also "touch" the 2 cells above, the 2 cells on the right and the 1 cell on the top right corner of the touched cell, as shown on the diagram below. If those cells are not on the screen (e.g. I pick the cell on the top right corner), they are not "touched", so in that case less than 5 extra cells are "touched".
I realize that most of the time I can still manage to finish the game "slowly", but my friends begin to laugh at my poor records. Of course you would agree with me that this is unfair - just compare the minimum number of cells I need to touch using their normal touch screens with that using my faulty touch screen. A more meaningful figure to reflect my speed would be the minimum number of touches required to finish a game divided by the time taken to finish that game. What if I can show this figure to my friends? Then they should understand that I am lightning fast...
The input starts with the number of games played g. Descriptions of g games follow. For each game, the first line consists of three positive integers m, n and t where m and n are at most 1000 and t is the time I took to finish the game (or the time I took before realizing that the game cannot be finished). Then the initial configuration of the game board is shown. A white cell is represented by the character 'w' and a black cell is represented by the character 'b'.
For each game, print the value of the minimum number of touches required to finish the game divided by the time taken to finish the game, correct to two decimal places. If the game cannot be finished, print "Impossible" instead.
5 5 1
5 5 1