Problem1295--射击

1295: 射击

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

不难发现,豆豆能从很多事情中去思考数学,于是豆豆父母决定让他去练习射击,这是项需要集中注意力的运动,相信能够让豆豆暂时脱离数学。学习射击的第一天就让豆豆产生了浓厚的兴趣,射击的靶子是大饼圆,射击枪的子弹近似圆柱,为什么要圆的不能是其他的形状呢,于是豆豆开始构思,设计了这样一个好玩的问题:

N*M 的方形格子靶子,每个格子有两种状态凸或者凹(如下图浅色表示凹,深色表示凸)

现在用一个十字横截面的子弹(填充黑色部分)去射击,被射中的小格子凹变凸,凸变凹,子弹放大后的横截面如下图


这种子弹最多可以覆盖 5 个格子,如图打完后,5 个格子凹凸状态发生了变化


请问最少需要几次射击使靶子中所有小格子都呈现凹的状态。

注意:子弹中心点如果打到四个角上则只会影响 3 个格子,如下图黑色格子表示被子弹中心点正好击中左上角后覆盖的 3 个格子,如果打到除四个角的边界上,则会影响到 4 个格子,如下图右侧的 4 个黑色格子所示,这是子弹中心点打中第 3 行第 6 列时的覆盖情况。(也就是说子弹超出靶子部分不起效)




Input

第一行两个用空格隔开的数字 N 和 M(1<=N,M<=17)

接下来 N 行描述靶子中小格子的状态,X’表示凸,.’表示凹。

Output

输出所需要的最少射击次数注意:输入数据保证有解

Sample Input Copy

5 5 
XX.XX
 X.X.X 
.XXX. 
X.X.X 
XX.XX 

Sample Output Copy

5

HINT

对于 30%的数据,1<=N,M<=4
 

Source/Category

2016nb