The Utrecht Youth Hostel has a giant dorm which usually accommodates all customers easily.
With NWERC in town, however, lots of people would like to stay there and all the space
available in the dorm should be used as efficiently as possible. You are assigned to provide
the dorm layout.
The size of the dorm is given and the layout should consist of a map of that particular
size. The map should display one ‘E’, the point of entrance of the dorm, and furthermore
‘B’s and ‘.’s, indicating beds and empty spaces. The entrance should be located somewhere
on the boundary of the dorm and every single bed should be reachable by starting at the
entrance and walking through empty squares only. You can only walk in vertical and horizontal
The provided layout should contain as many beds as possible.
On the first line one positive number: the number of testcases, at most 100. After that per
• One line with two integers l and w with 1 <= l,w <= 8: the size of the dorm.
• l lines with w characters: the dorm layout. Any layout with the maximum number of
beds is correct.
The 2007 ACM Northwestern European Programming Contest