Anti-bug before Chinese Valentine's Day
Time Limit: 1 Second Memory Limit: 32768 KB
August 22, 2004 is Chinese Valentine's Day. popo's girlfriend qoqo asks popo to see beautiful star field with her. qoqo takes a fancy to a lawn at the back-hill. But as popo known, there are some bugs in the lawn. It's a feature that it has bug (-_-). So popo is planning to sprinkle pesticide in advance. And now popo needs your help to calculate how much pesticide needed at least to kill all the bugs on the lawn.
Input
Two positive number n, m (2 <= n, m <= 8) in the first line of each test case, followed with n lines described the map of the lawn. In the map, 'o' indicates the grid which has bug in, '.' indicates the clean and clear grid. There are no other characters in the map.
n = m = 0 indicates the end of input.
Output
A bottle of pesticide can kill all the bugs in a range of 2*2 grids, output the minimal number of bottles of pesticide needed.
Sample Input
2 2 .. .. 3 3 o.. ..o .oo 0 0
Sample Output
0 2Submit
Source: ZOJ Monthly, January 2005