64 - The 8th Zhejiang University Programming Contest - 1002
Tom has a meadow in his garden. He divides it into N * M squares.
Initially all the squares are covered with
grass and there may be some squares that can't be mowed.
(Let's call them forbidden squares.)
He wants to mow down the grass on some of the squares.
He considers a meadow beautiful if and only if all these 8 rules are satisfied:
Here comes the problem. How many patterns of beautiful meadows he can get?
InputThis problem has several test cases. The first line of the input is a single integer T (1 <= T < 40) which is the number of test cases. And it will be followed by T consecutive test cases.
The first line of each test case is a single line containing 3 integers N (1 <= N <= 9) , M (1 <= M <= 9) and K (1 <= K <= N * M) which is the number of rows of the meadow, the number of columns of the meadow and the number of squares you can mow at most. Then N lines of input describe the rows of the meadow. Each of the N lines contains M space-separated signs "+" or "-" indicating whether the square can be mowed or not.
OutputFor each test case output an integer in a single line which is the number of the beautiful patterns.
2 1 1 1 + 1 2 2 + +