- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
Justiina ja Kotivalo ovat n \times m -kokoisessa sokkelossa. Sokkelossa voi liikkua lattiaruutuja pitkin pysty- ja vaakasuunnassa. Samassa ruudussa voi olla enintään yksi henkilö.
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
Osatehtävä 2 (72 pistettä)
- 3 \le n,m \le 1000