Problem Description
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.
Input
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.
Output
The output will consist of a single line for each field map containing the minimum number of shot needed to fill in all the empty hole.
Sample Input
6 7
.E.E...
...E.E.
.......
...E..E
.......
.....E.
2 2
EE
EE
Sample Output
2
2
