You have an N * M chessboard on which some squares are blocked out. In how many ways can you place one or more queens on the board such that no two queens attack each other? Two queens attack each other if one can reach the other by moving horizontally, vertically or diagonally without passing over any blocked square. At most one queen can be placed on a square. A queen cannot be placed on a blocked square.
Input:
The first line contains the number of test cases T. T test cases follow. Each test case contains integers N and M on the first line. The following N lines contain M characters each representing the board. A '#' represents a blocked square and a '.' represents an unblocked square.
Output:
Output T lines containing the required answer for each test case. As the answers can be really large, output them modulo 1000000007.
Constraints:
1 <= T <= 100
1 <= N <= 50
1 <= M <= 5
how to solve this using bitmask.
thank you.
Let's look to the first solution coming to the head:
Let's count DP[N][MSK1][MSK2][MSK3][MSK4][BMSK], where D[i][msk1][msk2][msk3][msk4][bmsk] is the number of the ways we can put queens on first i columns of the board, such that they stand on last 4 columns like it shown in bitmasks msk1, msk2, msk3 and msk4 and with condition that we can't put queen on positions, shown in mask bmsk: because there was some queens before, that are beating all the horizontals, shown in that bitmask.
We can step from state D[i][msk1][msk2][msk3][msk4][bmsk] to state D[i + 1][msk2][msk3][msk4][msk5][bmsk'] by going through all possible variants of msk5 and checking wheter such variant is possible, and changing bmsk to bmsk', if needed.
But it's too slooow dp: it has asymptotic O(n * 2^(6m)), it's about 5 * 1010.
Let's look on parameters msk1, msk2, msk3 and msk4. We see, that, we can't put more than 3 queens on one vertical: in other way two of that queens will be on neighbour fields and will beat one another. So we can use DP on broken profile (I don't know wheter I translated this Russian term correctly). Let's use mask that is equal to the vector (p1, ..., pk), where k is number of segments between blocked squares on that column.
As example, if column was like that: Q#_Q_, where _ is free field, # is broken, and Q is queen, we use as mask vector (1, 2).
For position _Q#Q_ we use vector (2, 1) (because first queen is on the second position on its segment, and the second queen - on the first).
For position Q#_#Q we use vector (1, 0, 1) (because there is no queen on second segment).
And so for each position. You can see, that each vector can be translated to the mask like that: (1, 0, 1) is 1 * (2 * 2) + 0 * (2) + 1, (2, 1) is 2 * (2) + 1, etc.
You can see, there is maximum 9 states for each column: 9 states can because if the central field is blocked, then there can be masks (a, b) for each 0 <= a <= 2 and 0 <= b <= 2;
So, there is a solution in N * 9^M * 2^M, that is about 95 millions.
It's pretty hard-coding problem. Where did you get that?
UPD:
Whooops. I didn't notice that there is multitest with 100 tests. Hmm. Is that problem from something like GCJ, where there is enough time to generate answer? If not, what is time-limit?
I think, there is another DP solution.
We will try to put queens row by row, column by column. Now we have two opportunities: to put a queen in some square in this row or not. So let's have 3 masks(m bits in every mask) - mask1, mask2 and mask3. The i'th bit of Mask1 will show, if there exists a queen, which attacks i'th square in current row and is situated above this square. The i'th bit of Mask2 will show, if there exists a queen, which attacks i'th square in current row and is situated on the same diagonal with this square, and additionally it is situated to the right comparatively to our square. The i'th bit of Mask3 will show, if there exists a queen, which attacks i'th square in current row and is situated on the same diagonal with this square, and additionally it is situated to the left comparatively to our square. We also need to know, if there is a queen, which is situated in our row and attacks our square(lets call this parameter F). If we know this information, we know if we can put queen to the current square and we can easily update our masks. So, we can calculate DP with parameters [CurrentRow][CurrentColumn][mask1][mask2][mask3][F].
The complexity is O(2^(3*m+1)*n*m). We have 100 tests, so the number of operationsis about 1600 millions, and it is not good. But we can see, that last bit of mask2 and first bit of mask3 is always 0, so we can keep only 4 bits in those masks. In such a way we build a solution, which will make about 400 millions operations. Time limit is 6 seconds, so I hope, this solution will run in time.
Sorry for my poor English.
UPD. Sorry, this solution is wrong. I'll try to modify it sooner, and if I'll get AC, I'll let you know.
So, I have AC now.
The main idea is DP + preprocessing. So, lets do a DP with states [CurrentRow][mask1][mask2][mask3]. Suppose, we have placed queens in our row is some way. We need to check some things:
1) Queens in our row do not attack each other.
2) Queens from previous rows do not attack queens in current row.
To check first condition let's do preprocessing before working with tests. For every possible row we will keep all possible queens placements, which satisfy first condition(we can represent them as masks in ternary system(0 - blocked square, 1- free square, 2 - queen)).
Second condition could be checked, using mask1, mask2 and mask3.
If both conditions are satisfied, we can process the next row.
We need to know, what will be new values of mask1, mask2 ad mask3 for next row. To do this we will also do a preprocessing for every pair <queens placement in a row,previous mask>
I know, that this explanation is not detailed, but if you have some question - you can ask me.