Nosaukums
Lamatas (spikes)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
52%

Definīcija

Gudrinieku ciemā plānots uzbūvēt jaunu banku. Lai nodrošinātu augstāko drošības sertifikāciju, ir jāapmierina prasība, kurā bankas galvenais seifs ir jānovieto telpā ar bīstamām lamatām. Lamatas tiek iebūvētas kvadrāta formas grīdas flīzēs. Tās tiek kontrolētas ar pulksteni kas cikliski skaita no 0 līdz 9, un tās ir aktīvas tieši tajā sekundē kad pulkstenis rāda Kij.
Lai nodrošinātu maksimālu drošību, seifa telpas plāns tiks izvēlēts nejauši no daudziem dizainiem. Taču, lai nodrošinātu, ka dizains ir drošs, nepieciešams noskaidrot, cik ilgā laikā seifu ir iespējams sasniegt. Zināms, ka no vienas flīzes uz citu iespējams nokļūt tieši vienā sekundē, kā arī, ka seifa telpu apmeklēs nultajā sekundē. Palīdziet bankai atrisināt šo problēmu!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā doti veseli skaitļi N un M ( 1 < N, M <= 1000), seifa telpas izmēri. 

Tālāk seko N rindas ar M kolonām kur katrā šūnā dots viens no simboliem:

  • Cipars Kij '0' līdz '9'  - Lamatas ar taimeri Kij
  • '#'   - Siena
  • '.'    - Grīda bez lamatām
  • 'A'   - Ieeja seifa telpā
  • 'B'   - Seifs

  


Izvaddatu raksturojums

Izvaddatos izvadiet vienu veselu skaitli - sekundes, cik ātri var nokļūt no ieejas līdz seifam vai 0, ja tas nav iespējams.


Paraugdati

Stdin
4 3
A12 
.#.
3#5
3.B
Stdout
7

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.