ZOJ Problem Set - 2916
You are going to participate in the television show 'lingo'. You are very confident that you will make the finals of the show. This is not only because you are well prepared, but also because you managed to find a way to use your pda unnoticed during the contest, and you have already written a program to help you with the bonuswords.
In the finals of the show, you first solve as many lingo words as possible within the allowed time. This determines how many balls you may take afterwards. The more balls you may take, the higher your probability is of winning the finals. But it is not easy to see what this probability is. Write a program to help you with this.
On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:
One line with the integers n (1 <= n <= 8) and k (0 <= k), where n is the size of the lingo grid and k is the number of words you solved in the first part of the finals.
n lines, with on each line exactly n characters. Each character will be either '*' or '.', representing a covered square and a numbered square respectively.
There will be at least k numbered squares on the board, and there is no row, column or diagonal covered yet.
For each test case:
One line with the percentage of getting lingo with either an absolute or a relative error of at most 10-6.
Source: The 2007 Benelux Algorithm Programming Contest