COCI 2009/2010, Contest #7

Task BAKICE

When it comes to trams, a lot of people are civilized individuals who know how to behave in one. However, there are always those few who upon spotting a place to sit will run towards it in supersonic speeds. If they spot more than one place, they always try the closest one first.

Problems arise when two or more such individuals aim for the same spot. If one of them is the closest, he or she will sit, and others won't event attempt to move in and instead turn their attention to the next closest spot. If however they are all equally close, they will all run to the seat resulting in a massive explosion that usually ends with complete destruction of both them and the seat.

You are given a description of one tram. It is represented as a table with R rows and C columns. The rude passengers are marked with the letter 'X'. Empty seats are marked with 'L' and the tram floor is marked with '.'. Note that although there are other passengers, the force projected by these idiots is more than enough to simply walk through them.

The distance between two cells is the Euclidean distance between their centers. Write a program that will determine the number of explosions which will take place before all people are seated, or destroyed, or they run out of chairs.

Input

The first line of input contains two integers, R (1 ≤ R ≤ 100) and C (1 ≤ C ≤ 100), number of rows and columns.

The next R lines contain C characters each. '.', 'X' or 'L'.

There will always be at least one character 'X' and at least one 'L' in the input. Also, there will be no two 'L' characters such that they are both equally distant to some 'X'.

Output

The first and only line of input should contain the number of explosion for the given layout.

Sample Tests

4 4
.LX.
.X..
....
.L..

1

4 4
.XLX
.X..
...L
.X..

2

7 7
...X.X.
XL....L
.......
...L...
.....XL
.......
...X...

1

All Submissions
Best Solutions

Point Value: 12
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)