Sahovska trka

View as PDF

Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 64M

Problem type

Tokom istraživanja starog hrama, Miloš je našao mističnu šahovsku tablu koja ima h redova i w kolona na kojoj su neka od polja blokirana uz pomoć magije. On je postao opsednut ovom tablom i krenuo da igra veoma neobičnu igru na njoj.

Na tabli se uvek nalazi tačno jedna figura koju Miloš u toku igre može da zamenjuje drugim figurama. Na početku igre to je kralj koji se nalazi na gornjem levom polju, (1,1). Figure se pomeraju po uobičajenim pravilima šaha, međutim nije moguće staviti ih na blokirana polja. Za svako pomeranje figure Milošu treba 1 sekund. Njegov cilj je da što pre stavi neku figuru na donje desno polje, (h,w).

U proizvoljnom momentu Miloš može da zameni trenutnu figuru nekom drugom figurom na istoj toj poziciji. Međutim, on ne može ovo da uradi trenutno, nego mu za to treba određeno vreme, u zavisnosti od toga koju novu figuru počinje da koristi.

Kralj : Milošu treba 1 sekund da zameni bilo koju figuru kraljem.
Kralj se u jednom potezu može pomeriti na jedno od 8 susednih polja ako to polje nije blokirano.




Lovac: Milošu treba 2 sekunde da zameni bilo koju figuru lovcem.
Lovac se u jednom potezu može pomeriti dijagonalno proizvoljan broj polja, sve dok ni jedno od polja na njegovom putu nije blokirano.



Top: Milošu treba 3 sekunde da zameni bilo koju figuru topom.
Top se u jednom potezu može pomeriti levo, desno, gore ili dole proizvoljan broj polja, sve dok ni jedno od polja na njegovom putu nije blokirano.



Konj: Milošu treba 4 sekunde da zameni bilo koju figuru konjem.
Konj se u jednom potezu može pomeriti 2 polja u proizvoljnom od četiri smera (gore, dole, levo, desno) i 1 polje u jednom od dva smera ortogonalna na prethodni smer. Nije bitno da li su polja preko kojih konj usput prelazi blokirana ili ne.


Kraljica: Milošu treba 5 sekundi da zameni bilo koju figuru kraljicom.
Kraljica, u jednom potezu, može da se pomeri levo, desno, gore, dole ili dijagonalno proizvoljan broj polja, sve dok ni jedno od polja na njenom putu nije blokirano.


Pomozite Milošu i recite mu za koliko najmanje sekundi može da završi ovu igru, ili mu saopštite da to nije moguće.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se dva prirodna broja h i w, koji obeležavaju redom visinu i širinu table. U narednih h redova se nalazi niz dužine w koji se sastoji samo od karaktera . i #, gde . označava da je polje slobodno, a # da je polje blokirano.

Opis izlaza

Na izlaz ispisati ceo broj t, najmanji broj sekundi da Miloš postavi figuru na polje (h,w), odnosno -1 ako to nije moguće.

Primer 1

Ulaz
3 3
...
.#.
...
Izlaz
3

Primer 2

Ulaz
3 5
.####
##.##
####.
Izlaz
6

Primer 3

Ulaz
10 10
...#.###..
.....#####
...##..#.#
#....#....
.#.......#
##..#.....
......#...
..##..#.#.
..#..#..#.
..#..##...
Izlaz
8

Objašnjenje primera

Primer 1:

Primer 2:

Primer 3:

Ograničenja

  • 1 \leq h,w \leq 500

Test primeri su podeljeni u 5 disjunktnih grupa:

  • U test primerima vrednim 10 poena: h,w \leq 5.
  • U test primerima vrednim 10 poena: h,w \leq 200 i ako postoji rešenje, postoji i optimalno rešenje koje ne zahteva zamenu figura.
  • U test primerima vrednim 40 poena: h,w \leq 200.
  • U test primerima vrednim 10 poena: Ako postoji rešenje, postoji i optimalno rešenje koje ne zahteva zamenu figura.
  • U test primerima vrednim 30 poena: Bez dodatnih ograničenja.

Comments

There are no comments at the moment.