- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
Kahden ruudun välinen etäisyys on Manhattan-etäisyys, eli kun ruudut ovat $(y_1,x_1)$ ja $(y_2,x_2)$, niiden etäisyys on $|y_1-y_2|+|x_1-x_2|$.
Tehtäväsi on selvittää, kuinka lähelle toisiaan Justiina ja Kotivalo voivat päästä, jos he liikkuvat optimaalisesti.
Syöte
Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: sokkelon korkeus ja leveys.
Tämän jälkeen tulee sokkelon kuvaus: $n$ riviä, joista jokaisella on $m$ merkkiä. Merkki voi olla
.
(lattia), #
(seinä), A
(Justiinan alkukohta) tai B
(Kotivalon alkukohta).Voit olettaa, että jokainen reunaruutu on seinää ja merkkejä
A
ja B
on molempia tasan yksi syötteessä.Tuloste
Tulosta yksi kokonaisluku: pienin mahdollinen etäisyys.
Esimerkki 1
Syöte:
5 8
########
#A#.#.B#
#.#.####
#...#..#
########
Tuloste:
2
Esimerkki 2
Syöte:
5 8
########
#A#...B#
#.#.####
#...#..#
########
Tuloste:
1
Osatehtävä 1 (28 pistettä)
- $3 \le n,m \le 20$
- $3 \le n,m \le 1000$