COCI '09 Contest 7 #3 Bakice

View as PDF

Submit solution


Points: 12
Time limit: 0.6s
Memory limit: 32M

Problem types

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 at 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 even 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 Specification

The first line of input contains two integers, R (1 \le R \le 100) and C (1 \le C \le 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 Specification

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

Sample Input 1

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

Sample Output 1

1

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

1

Comments

There are no comments at the moment.