Casino

Time limit: 0.5s Memory limit: 64MB Input: Output:

Cerință

Într-o țară de la marginea lumii, guvernul a descoperit că există o problemă reală în ceea ce privește prezența cazinourilor și a sălilor de jocuri de noroc prea aproape de locații precum școli, spitale sau alte locuri de interes public.

Deoarece această țară este una a tuturor posibilităților, un funcționar public a propus mutarea cazinourilor pentru a fi cât mai departe de școli.

Totuși, avem o problemă majoră, anume faptul că în această țară, reprezentată ca o matrice cu nn linii și mm coloane, există deja foarte multe cazinouri deschise, iar mutarea lor ar fi imposibilă din punct de vedere practic și logistic, așa că s-a găsit o soluție de rezervă.

Practic, obiectivul nostru este să mutăm școala din această țară undeva pe matrice, astfel încât să fie cât mai departe de cazinouri. Cu alte cuvinte, vrem ca cel mai apropiat cazino să fie cât mai departe posibil.

Date de intrare

Pe prima linie se dau nn și mm, numărul de linii și coloane a matricii. Pe următoarele nn linii se află descrierea matricii, unde cu C sunt notate cazinourile, iar cu . spațiile libere.

Date de ieșire

Să se afle distanța minimă maximă față de un cazino a unei amplasări optime a școlii.

Restricții și precizări

  • 1n10001 \leq n \leq 1000.
  • 1m10001 \leq m \leq 1000.

Exemplu

stdin

5 6
C.....
...C..
......
......
....C.

stdout

4

Log in or sign up to be able to send submissions!