问题1594--射击

1594: 射击

时间限制: 1 Sec  内存限制: 128 MB
提交: 75  解决: 41
[提交] [状态] [讨论版] [命题人:]

题目描述

不难发现,豆豆能从很多事情中去思考数学,于是豆豆父母决定让他去练习射击,这是项需要集中注意力的运动,相信能够让豆豆暂时脱离数学。学习射击的第一天就让豆豆产生了浓厚的兴趣,射击的靶子是大饼圆,射击枪的子弹近似圆柱,为什么要圆的不能是其他的形状呢,于是豆豆开始构思,设计了这样一个好玩的问题: 
N*M的方形格子靶子,每个格子有两种状态凸或者凹(如下图浅色表示凹,深色表示凸)

输入

第一行两个用空格隔开的数字N和M(1<=N,M<=17) 
接下来N行描述靶子中小格子的状态,‘X’表示凸,‘.’表示凹。

输出

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

样例输入 Copy

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

样例输出 Copy

5

提示

样例2:
8 9
..XXXXX..
.X.....X.
X..X.X..X
X.......X
X.X...X.X
X..XXX..X
.X.....X.
..XXXXX..
输出2:
25
对于30%的数据,1<=N,M<=4

来源/分类