Problem B
Warehouse
Input: Standard Input

Output: Standard Output

A number of boxes is to be moved in a warehouse. The warehouse can be modeled as a grid where each square is the equal to the size of a box. Consider the model below: (‘B’ = box to be moved, ‘.’ = empty square, ‘X’ = position a box should occupy after the move, ‘#’ = obstacle)

BBBB....

.###...X

.XX#...X

...#....

........

A box may be moved to any of its four neighboring squares, assuming this square is empty (that is, not occupied by another box or an obstacle). To move a box takes one unit of time, and only one box may be moved per time unit. Your task is to determine the least amount of time to move all boxes to their destination squares. You may assume that a solution exists. Number of boxes will be no more than 15.

Input

The first line in the input contains the number of test cases (at most 20). Each case starts with a line containing two integers, the height (1 ≤ h ≤ 40) and width (1 ≤ w ≤ 40) of the grid. Then follows h lines, each containing w characters, describing the grid in the format above.

Output

For each test case, output a line containing a single integer: the minimum number of time units to move all boxes.

Sample Input                               Output for Sample Input

1

5 8

BBBB....

.###...X

.XX#...X

...#....

........

Problem setter: Jimmy Mårdell

Special Thanks: Mohammad Sajjad Hossain

test case:
5
5 8
BBBB....
.###...X
.XX#...X
...#....
........
5 8
....#...
....#...
B..X#B.X
....#...
....#...

題目簡單地要求二分圖匹配權重總合最小。

位元的狀態壓縮，把已經匹配過的點當做1, 沒有則0, 因此最多 15 bits。

dp 的方法：

依序放入X團的點，然後Y團匹配過的會變成一個狀態，從狀態中沒被匹配過的點進行鬆弛。