Problem F
Black and White
Input: Standard Input
Output: Standard Output
Time Limit: 10 Seconds
Given a partially filled grid with M rows and N columns, you are to calculate how many ways there are to fill the remaining part of the grid under the constraints stated below, and output one of these ways (if any exist).
Each cell in the grid should be colored either black or white. All black cells in the grid should be connected with each other, and all white cells should also be connected with each other. The pictures below show two filled grids where this constraint is only fulfilled in the right picture.
|
|
|
Furthermore, there must be no 2x2 blocks in the grid which consists of only white cells, or of only black cells. The picture below to the left shows a grid with a black and a white 2x2 block, while the grid below to the right contains no such 2x2 block.
|
|
|
You are not allowed to change the color of any of the cells whose color has already been assigned in the input, and all cells must be colored
Input
The first line in the input contains an integer T (less than 100), the number of cases to follow. Each case starts with two integers, M and N (2 ≤ M, N ≤ 8), the number of rows and columns respectively in the grid. The next M lines contains N characters each and describes the grid using the following characters:
# - a cell which
is colored black
o - a cell which is colored white
. - a cell which color has not yet been
assigned
Output
For each case, first output the number of ways to fill the grid. If there are at least one way, you should also output one of these ways, using the same format for the grid as in the input. Output a blank line after each case.
Sample Input Output for Sample
Input
43 3o.. .##...5 5..#...........oo.... .#...7 5.......o..#...........o.....#.o.... 2 3###oo# 6 8 ........ ........ ........ ........ .#...... ........ |
4oo# o##oo# 0176######ooo####oo#o##o#oooo####oooooo 1###oo# 71582 #ooooooo #o#####o #ooooo#o #o#o#o#o #######o #ooooooo |