2014
02-12

# Everyone is No.1

Everyone is No.1—— As long as there is belief in my heart, I will hold on until the last moment. Real hero, spirit never die!

See Figure 1, Teddy was in the left-up point, a ‘E’ represents a hole. Now, Teddy want to fill in all the hole. He has a special soil gun. When he shot, it can spread right or down at any time and fill the hole when it get through it, every shot must stop at the right-down point. See figure 2, Teddy should shot three times, but the more optimal solution was in the figure 3.

Figure 1

Figure 2                                     Figure 3

Your task is to create a program that will determine the minimum number shots needed to fill all the hole, if you can’t have any solution about it, don’t fell sorry. Because Everyone is No.1, you can solve other problems first , then return to this problem, you will see it can be so easy.

The input consists of one or more field maps. A field map consists of two parts:
Firstly, two integers n, m ( 1 <= n, m <= 24)
Secondly, a nXm matrix represent the map.

‘E’ represent the empty hole.
‘.’ represent the soil.

The input consists of one or more field maps. A field map consists of two parts:
Firstly, two integers n, m ( 1 <= n, m <= 24)
Secondly, a nXm matrix represent the map.

‘E’ represent the empty hole.
‘.’ represent the soil.

6 7
.E.E...
...E.E.
.......
...E..E
.......
.....E.

2 2
EE
EE

2
2

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮