ZOJ Problem Set - 2292
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.
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.
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.
Author: ZHENG, Jianqiang
Source: ZOJ Monthly, January 2005