Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3723
Starfruit

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Plants VS Zombie is an interesting game, recently Edward has become totally addicted to playing this game. There are many kinds of plants he can choose to defend zombies, but what Edward interests most is a kind of plants called Starfruit. As we know, most plants stand toward right and only can attack zombies those are precisely on its right. However, starfruit is much more powerful, it can sparks little stars towards five directions!

Edward is so interested in this fruit that he wrote a game with nothing but starfruit. Unfortunately, something beyond exception happened, that starfruit now only can attack less than 3 units distance(by Euclidean distance), also he made a mistake with directions: now starfruits spark towards up, left, right, lower left and lower right(not as usual in PVZ). What's more, now starfruit attacks each other!

As Edward likes statfruit very much, he wants to put as more starfruit into the map as possible, but if you place a starfruit on a lattice attacked by another starfruit, it will die and disappear immediately. So now he wants to know the maximum number of starfruits can be placed on the map, but recently he's busy preparing Summer Camp so he turns to your help.

Input

The input consists of several cases. Each case starts with a line contains two integer n(1≤n≤1000) and m(1≤m≤12), indicates that it's a map of width m and height n. Then follows n lines each with m characters, which is either 'X' or '.'. A '.' means you can put starfruit on it, A 'X' means there is a rock there so that you can't put anything on it, also the stars sparked by starfruits can't across a rock.
Input ends when both n and m equals to 0. This case will not be executed.

Output

For each case, output the maximum number of the starfruit you can put.

Sample Input

3 3
...
XX.
...
0 0

Sample Output

3

Hint

  • All lattices are squares of one unit, both starfruit and rock are considered at the center of the lattice.
  • The answer to the sample: ('O' means starfruit)
      O..
      XXO
      O..
  • If a map like this and 'O' is a starfruit, we consider point A and B are been attacked.
      OX.
      XA.
      ..B


Author: LIN, Chengyuan
Contest: ZOJ Monthly, June 2013
Submit    Status