Bhagat Singh is on a mission to rescue our patriotic leaders from the jail which are caught by Britishers.
Jail is a grid of size of N*M in which each cell is a prison cell and they are interconnected from all the directions. There is only one exit in the grid. Since you cannot give instruction to an individual leader, you'll broadcast the message for there movement. Likewise Left, Right, Down or Up. Everyone will move in that direction. If they go out of the grid than they will be caught and shot dead. You want the maximum number of people to get out from the exit.
Help Bhagat Singh and save our patriotic leaders.
Input:
The first line contains N and M size of grid (N*M). and subsequent N line will describe M prision cell and exit.
N M
A11A12 ......A1m
.......
An1 ...............Anm
Where Aij is:
'.' : Cell is Empty
'L' : Leader in cell
'E' : Exit (Only one exit.)
Output:
The maximum number of leaders that can be rescued.
Constraints:
1 <= N, M <= 50
Here, we'll broadcast message as to go left.
Everyone will go left, then prison will look like this. (1 Leader reached exit)
| . | L | . |
| . | E | . |
| L | L | . |
afterward,
Broadcast message to go above. (1 Leader reached exit)
| . | . | . |
| L | E | . |
| . | . | . |
lastly,
Broadcast message to go right. (1 Leader reached exit)
| . | . | . |
| . | E | . |
| . | . | . |
No more Leaders to save.
3 People were able to escape from the Jail. and rest all went outside the grid and shot.
