Problem: brute2
As a scarecrow salesman, farmers often ask you how many scarecrows they will need to protect their fields. Although your boss would like you to respond with "Many, many expensive scarecrows," you are honest and will only sell them as few scarecrows as necessary. This year, corn has grown particularly well, up past the height of any scarecrows. Crows have particularly good vision, but can only reliably be frightened by a scarecrow if it is visible along a row, column or diagonal in the cornfield. Farmers come to you with a map of their cornfield so that you know which plants are worth saving. Given a map of an N×M rectangular cornfield, you must determine the fewest number of scarecrows required to protect all sections worth protecting.
Input
The input consists of many test cases, followed by a single '0' on the last line to signal the end of the tests. Each problem starts with a line containing two integers N and M, 1 ≤ N,M ≤ 9, the dimensions of the cornfield. The following N lines contain M characters each: an area is either marked with an 'X' if the area is worth saving, or '.' if it isn't.
Output
For each test case, print the field number and the minimum number of scarecrows required to protect it.
Sample Input
7 7 XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX XXXXXXX 6 8 X..X.... .X...X.. ..X..... ...X.... ....X... .....X.. 0
Sample Output
Field 1: 4 Field 2: 1