Zadanie
Konečne deň, na ktorý sa Emo celý rok tešil – Silvester. Tento rok ho chce stráviť na internáte v Bratislave. Keď sa to dozvedel jeho kamarát, neodpustil si štipľavú otázku, či už má nakúpené ohňostroje1. Emo iróniu nepochopil a tak, keďže nemal, začal narýchlo nejaké zháňať.
Zobral auto a šup ho na cesty. Ešte sa vo svojom rodnom meste2 zastavil v obchode s pyrotechnikou a minul tam takmer celú výplatu. Odtiaľ už išiel priamo do Bratislavy.
Keď zišiel z diaľnice, zastavil sa ešte na benzínke. Ako tak tankoval, započúval sa do rádia a takmer dostal infarkt. Práve totiž išli správy o situácii v Bratislave:
Za púšťanie rakiet v Bratislave hrozí veľká pokuta.
Keďže policajti očakávajú v tento deň veľký počet výtržností3, vymysleli si systém ako mať všetko pod kontrolou. Po meste na náhodné pevne určené miesta umiestnili policajné kontroly, kde kontrolujú obsah každého auta. Nemôžu dať síce pokutu za to, že niekto ohňostroj prepravuje, ale môžu si ho poznačiť a navštíviť večer.
Aby bolo ťažké sa kontrole vyhnúť, na každej križovatke, kde nie je kontrola, stojí policajt ukazujúci len jeden prípustný smer jazdy. Každému, kto by z takejto križovatky chcel odísť iným, než povoleným smerom, dá pokutu (ale nechá ho ísť).
Emo si nejakú tú raketku neodpustí. Cesta na intrák tak preňho nebude iba o šoférovaní. Potrebuje v prvom rade zistiť kade má na intrák ísť tak, aby minul čo najmenej peňazí na pokuty.
Rýchlo preto zavolal Zajovi, nech mu pomôže. Zajo je totiž rodený Bratislavčan a má prístup k informáciám, o ktorých iní môžu len snívať. Potrebuje však vašu pomoc, aby vedel Emovi rýchlo odpovedať skôr ako si niekto všimne, že ešte aj telefonuje za volantom!
Úloha
Pre účely tejto úlohy budeme Bratislavu považovať za obdĺžnik \(r \times s\) križovatiek. Na každej križovatke sa dá prejsť rovno, odbočiť vpravo, vľavo, aj otočiť sa.
Existujú križovatky nasledovných typov:
Križovatky s prikázaným smerom odjazdu: tieto križovatky majú len jeden povolený smer odjazdu. Ak z nich Emo odíde iným ako povoleným smerom, dostane pokutu. Veľkosť tejto pokuty môže byť rôzna pre rôzne smery. Napríklad pre križovatky s prikázaným smerom odjazdu hore môže byť iná pokuta ako pre križovatky s prikázaným smerom odjazdu dole.
Križovatky s kontrolou: tieto križovatky nemajú žiadne obmedzenia na to, ako cez ne môžete jazdiť, ale policajti na nich kontrolujú obsah kufra. Ak Emo počas cesty na internát prejde čo i len cez jednu takúto križovatku, o polnoci bude musieť zaplatiť pokutu za odpálenie rakety. Ak Emo prejde cez viacero takýchto križovatiek, bude platiť rovnako veľa, ako keby prešiel len cez jednu.
Križovatka s internátom: táto križovatka je Emov cieľ. Prikázaný smer odjazdu z tejto križovatky nás nezaujíma, lebo Emo z tejto križovatky už nechce ísť ďalej.
Križovatka s benzínkou: na tejto križovatke Emo začína a nie je tam ani kontrola, ani prikázaný smer odjazdu.
Na niektorých políčkach obdĺžnika nie sú križovatky, ale Dunaj. Sem sa Emo s autom nikdy nechce dostať!
Dostanete popis situácie v Bratislave a aj veľkosti jednotlivých pokút. Zistite, koľko najmenej môže Emo zaplatiť na pokutách, ak chce prísť na internát a o polnoci tam odpáliť raketu. Počas svojej cesty nemôže opustiť Bratislavu.
Nepredpokladajte, že sa v Bratislave dá dostať na každú križovatku bez porušenia predpisov! Dokonca je možné, že na niektorých križovatkách je prikázaný smer jazdy do Dunaja.
Formát vstupu
Na prvom riadku vstupu dostanete medzerami oddelené postupne veľkosti pokút \(P_O, P_L, P_P, P_H, P_D\): veľkosť pokuty za ohňostroj (ktorú Emo zaplatí, ak prejde cez nejakú kontrolu) a za porušenie prikázaného smeru odjazdu vľavo, vpravo, hore a dole. Všetky pokuty sú celé čísla z rozsahu \(0\) až \(10^{12}\) (vrátane).
Nasleduje riadok s rozmermi mapy \(r, s\) (\(1 \leq r \cdot s \leq 100\,000\)). Ďalej nasleduje \(r\) riadkov po \(s\) znakoch popisujúcich samotnú Bratislavu. Každý z týchto znakov určuje typ jednej križovatky.
Znaky popisujúce križovatky môžu byť nasledovné: K
– križovatka s kontrolou; E
– križovatka s benzínkou, kde Emo začína; I
– križovatka s internátom (cieľ); L, P, H, D
– križovatky s prikázaným smerom odjazdu vľavo, vpravo, hore alebo na dole; ~
– Dunaj.
Môžete predpokladať, že na mape sa aj intrák aj Emo nachádzajú práve raz.
Formát výstupu
Vypíšte, koľko najmenej môže Emo zaplatiť na pokutách, ak sa chce dostať na intrák a o polnoci tam odpáliť raketu. V prípade, že neexistuje cesta vypíšte -1
.
Hodnotenie a obmedzenia
Pre jednotlivé sady testov navyše platia nasledovné obmedzenia. Za vyriešenie každej sady získate 1 bod.
číslo sady | križovatky typu K |
veľkosti pokút | rozmery mapy |
---|---|---|---|
1 | na mape nie sú | pokuty sú 0 | \(2 \leq r \cdot s \leq 50\) |
2 | na mape nie sú | pokuty sú buď 0 alebo 1 | \(2 \leq r \cdot s \leq 100\,000\) |
3 | na mape nie sú | pokuty sú ľubovoľné | \(2 \leq r \cdot s \leq 70\) |
4 | na mape nie sú | pokuty sú ľubovoľné | \(2 \leq r \cdot s \leq 100\,000\) |
5 | na mape sú | pokuty sú ľubovoľné | \(2 \leq r \cdot s \leq 10\,000\) |
6 | na mape sú | pokuty sú ľubovoľné | \(2 \leq r \cdot s \leq 100\,000\) |
Príklad
Input:
10 10 1 6 4
4 3
HLL
IPK
D~H
DLE
Output:
8
Optimálna cesta na internát vyzerá nasledovne: Z benzínky pôjde Emo doľava, pričom neplatí žiadnu pokutu, lebo na benzínke policajti nie sú. Potom pôjde opäť doľava, pričom opäť neplatí pokutu, lebo odišiel povoleným smerom. Následne pôjde dvakrát nahor, pričom oba razy poruší prikázaný smer jazdy nadol, teda dvakrát zaplatí pokutu \(4\). Keďže Emo neprešiel cez žiadnu kontrolu, o polnoci nedostane žiadnu pokutu.
Input:
1 2 3 4 5
2 2
E~
~I
Output:
-1
Emo môže rovno odparkovať, nikam sa nedostane.
Input:
1000 1 2 3 4
4 6
DHHHPK
LELKHK
~P~PKL
PKLHI~
Output:
1001
Kontrole sa cestou na internát nedá vyhnúť. Optimálne je ísť najprv trikrát doprava, potom hore, doprava, dvakrát dole, doľava a dole. Všimnite si, že po ceste Emo prejde až cez štyri kontroly, pokutu za odpaľovanie ohňostrojov však aj tak zaplatí iba raz. Okrem toho ešte poruší jeden prikázaný smer odjazdu vľavo, takže dokopy na pokutách zaplatí \(1000 + 1 = 1001\).
Na začiatku si ukážeme jedno korektné riešenie, ktoré síce správne vyrieši každý vstup, no je príliš pomalé pri veľkých rozmeroch. Na toto riešenie ďalšie nenaväzujú, preto, ak chcete, môžete toto preskočiť (bude označené hviezdičkou). Následne si ukážeme, ako bolo možné využiť spomínané obmedzenia na jednotlivé sady a na záver si predstavíme algoritmus, ktorý rýchlo a správne vyrieši všetky sady vstupov.
Pri implementácii všetkých riešení používame dva triky často používané pri úlohách s mriežkami: zarážky a polia zmien súradníc k susedom. Ak ste sa s týmito trikmi doteraz nestretli, viac sa o nich dozviete v Kuchárke.
Bratislava ako bludisko (*)
Predstavme si Bratislavu, ktorú dostaneme na vstupe, ako bludisko. Ako nájsť cestu z bludiska? Jedna z možností je predstaviť si, že máme k dispozícii niť, ktorou si značíme kade chodíme1. Na každej križovatke odbočíme doprava. Akonáhle prídeme do slepej uličky alebo na miesto, kde sme už boli, vrátime sa späť a pôjdeme odbočkou, ktorou sme ešte nešli a zároveň je najviac napravo. Tento postup opakujeme, kým sa z bludiska nedostaneme von.
Pokúsme sa aplikovať tento postup na hľadanie najlacnejšej cesty na intrák. Potrebujeme si pri každom odbočovaní rátať sumu doteraz zaplatených pokút, a že či sme prešli cez nejaké kontroly. Ako niť použijeme pole booleanov vis
. Na riešenie použijeme rekurzívnu funkciu, ktorá bude prehľadávať všetky cesty. Nech sme na políčku \((x, y)\). Ak je toto cieľové políčko, tak sme vyhrali a stačí nám obnoviť globálnu premennú, v ktorej si udržiavame cenu doteraz najlacnejšej nájdenej cesty do cieľa. V opačnom prípade skontrolujeme, že či toto políčko náhodou nie je Dunaj alebo políčko, na ktorom sa nachádza naša niť. V takom prípade nechcem ďalej pokračovať v ceste a vraciame sa späť. Inak nastavíme vis[x][y] = true
a skúšame sa rekurzívne zavolať na všetkých susedov tohto políčka. Vracanie sa po niti predstavujú návraty z rekurzívnych volaní. Pri návrate z rekurzívneho volania sa pokúsime ísť ďalším smerom. Ak už sme prešli všetky smery, tak nastavíme vis[x][y] = false
, čo prestavuje to, že niť sa už na tomto políčku nebude nachádzať, lebo ideme späť. Tento algoritmus sa volá aj backtracking.
Časová a pamäťová zložitosť
Riešenie backtrackingom je pekné a jednoduché, ale má jednu nevýhodu – je pomalé (samozrejme aj pomalé, správne riešenie dostane nejaké body). Cesta, pri ktorej Emo najmenej minie môže byť ozaj ktorákoľvek, a teda musíme vyskúšať všetky, ktoré existujú. Na každej križovatke rozoberieme 4 možnosti. Pre každú možnosť rozoberieme na ďalšej križovatke 4 možnosti, atď. Časová zložitosť tohto riešenia je teda \(O(4^{rs})\). Pamäťová zložitosť je \(O(r \cdot s)\) – veľkosť mapy Bratislavy a hĺbka zásobníka pri rekurzii.
Výsledný program by mohol vyzerať takto:
// B = mapa Bratislavy
// vis = nasa niť, pole vis urcuje ci sme na krizovatke uz boli
// surX = suradnica x, surY obdobne
// vysledok = cena doteraz najlacnejsej cesty
// pair<> I = suradnice internatu
long long vysledok = NEKONECNO;
void spocitaj(int surX, int surY, long long cena, bool presli_kontrolu) {
// Ak som tu uz na tejto ceste boli alebo tu je dunaja.
if (vis[surX][surY] || B[surX][surY] == DUNAJ) return;
// Dosli sme uz do ciela?
if (surX == I.first && surY == I.second) {
// Ako vysledok zoberieme minimum z doterajsieho vysledku
// a terajsej ceny, ku ktorej pripocitame pokutu
// za ohnostroje v pripade, ze sme presli cez nejake kontroly.
vysledok = min(vysledok, cena + (presli_kontrolu ? Po : 0));
return;
}
// Zaznacime si, ze sme tu boli.
vis[surX][surY] = true;
// Odbocime postupne do kazdeho smeru.
for(int i=0; i<4; ++i) {
// Od nasho policka ideme smerom i, teda x zvysime o dx[i] a y o dy[i].
// Cenu zvysime o pokutu za tento smer, co nam urci funkcia zisti_cenu.
// Ked jej hodime krizovatku na ktorej sme a smer ktorym chceme ist.
// Tiez musime updatovat flag s kontrolami.
spocitaj(surX + dx[i],
surY + dy[i],
cena + zisti_cenu(B[surX][surY], i),
presli_kontrolu || (B[surX][surY] == KONTROLA));
}
// Odchadzame z krizovatky, zaznacime, ze sme tu este neboli,
// nech sem vieme prijst znova.
vis[surX][surY] = false;
}
Predstava Bratislavy ako grafu
Bratislava sa dá predstaviť ako orientovaný ohodnotený graf. Križovatky sú vrcholy. Hrana z križovatky \(a\) vedie do križovatky \(b\), ak sú tieto križovatky susedné. Ohodnotenia hrán sú pokuty, ktoré Emo zaplatí, ak prejde medzi týmito dvoma križovatkami. Hrany sú orientované, lebo hoci sa Emo vie dostať aj opačne, môže to byť za inú pokutu. Ak je odbočenie zadarmo (v smere prikázaného smeru, prípadne z križovatky bez obmedzení), pridáme hranu s nulovou cenou. Z Dunaja hrany nepridávame. Kontroly zatiaľ neuvažujeme.
V tejto interpretácii je našou úlohou nájsť najlacnejšiu cestu v grafe, na čo existujú rozumne rýchle algoritmy.
Čo ak pokuty neexistujú?
V prvej sade vstupov sa pokuty nenachádzali. V našej predstave to znamená, že všetky ceny v grafe sú nulové, a teda celková cena bude buď 0
ak existuje cesta na intrák, prípadne -1
ak neexistuje.
Ako zistiť, či nejaká cesta existuje? Jedna z možností je použiť algoritmus prehľadávania do hĺbky. Tento algoritmus sa podobá backtrackingu, ktorý sme si vysvetlili pri pomalom riešení. Jediný rozdiel je, že keď pri vynáraní sa z rekurzie opúšťame nejaký vrchol, necháme ho označený ako navštívený. Toto nám zaručí, že každý vrchol navštívime iba raz a časová zložitosť bude \(O(r \cdot s)\). Takéto zrýchlenie si môžeme dovoliť urobiť vďaka tomu, že teraz na nájdenie najlacnejšej cesty nepotrebujeme vyskúšať všetky možnosti, keďže každá cesta je rovnako dobrá (má cenu nula). Ako a prečo to celé funguje sa dočítate v Kuchárke.
Inou rovnako rýchlou možnosťou je použiť iný základný grafový algoritmus – prehľadávanie do šírky (známe tiež pod anglickým názvom breadth-first search, BFS).
Čo sa zmení, keď pridáme pokuty veľkosti 1?
Nakoľko už budeme chcieť nájsť aj reálne najlacnejšiu a nielen tak hocijakú cestu, prehľadávanie do hĺbky nám už nepomôže. Prehľadávanie do šírky však vieme rozumne vylepšiť tak, aby nám pre dva druhy cien – jednu nulovú a druhú nejakú inú (napr. 1) hľadalo najlacnejšiu cestu.
Princíp prehľadávania do šírky sa opiera o to, že sa používa fronta. Vďaka nej vieme nájsť najlacnejšiu cestu v grafe, kde sú všetky hrany rovnakej dĺžky. Pri BFS platí, že v každom momente sú vrcholy vo fronte usporiadané podľa ceny, ktorou sa do vrcholu vieme dostať.
Predstavme si teraz, že nebudeme využívať frontu, ale obojsmernú frontu. Táto dátová štruktúra nám umožňuje pridávať prvky aj na začiatok, aj na koniec. Ak vedie do vrcholu nulová hrana, pridáme ho na začiatok. Ak doňho vedie jednotková hrana, pridáme ho na koniec. Všimnite si, že takýmto spôsobom udržiavame vrcholy vo fronte utriedené podľa dĺžky najkrajšej cesty.
Tento algoritmus sa tiež zvykne označovať ako 0/1 BFS. Časová zložitosť je rovnaká ako pri klasickom BFS, \(O(r \cdot s)\), pamäťová takisto.
Ale pokuty predsa môžu byť ľubovoľné…
Teraz sa pozrime na prípad, keď dĺžky hrán môžu byť ľubovoľné. Potrebujeme dátovú štruktúru, do ktorej vieme rýchlo pridávať prvky a vyberať z nej najmenší prvok. V prípade nulových a jednotkových hrán nám obojsmerná fronta postačila. Vo všeobecnom prípade budeme potrebovať zbraň vyššieho kalibru. Vhodnou dátovou štruktúrou je napríklad halda. Použitím haldy vlastne získame Dijkstrov algoritmus na hľadanie najlacnejšej cesty. Dostaneme tak rýchle riešenie v časovej zložitosti \(O(rs \cdot \log (rs))\) (počet vrcholov je \(r \cdot s\) a počet hrán je \(4 \cdot r \cdot s\)). Pamäťová zložitosť je \(O(r \cdot s)\) – veľkosť mapy a v najhoršom prípade aj veľkosť haldy.
Čo s kontrolami?
Stále sme si však od testovača zarobili len 4 body zo 6-tich. Potrebujeme ešte vyriešiť ako naložiť s križovatkami, kde prebiehajú kontroly.
Najjednoduchšie riešenie je uvedomiť si nasledovné: Emo buď dostane pokutu za ohňostroj, alebo nedostane. Celé prechádzanie bludiskom môžeme extrahovať do funkcie a túto dvakrát zavolať – raz s tým, že nebudeme chodiť cez žiadne kontroly (a nezaplatíme pokutu za ohňostroj) a raz s tým, že môžeme prejsť cez ľubovoľne veľa kontrol, ale na konci pripočítame veľkosť pokuty za ohňostroj. Časovú zložitosť to nezhorší. Celé to robíme len dvakrát, čo je konštanta. Navyše, v podstate rozoberáme len dva jednoduché prípady.
Na demonštráciu tohto riešenia uvádzam zdrojový kód, ktorý podrobnejšie ukazuje, čo sme si práve opísali. Funkcii spocitaj
realizuje Dijkstrov algoritmus. Premenná flag
hovorí, či má ísť aj cez kontroly alebo sa k nim má správať rovnako ako ku križovatkám s Dunajom.
#include <iostream>
#include <vector>
#include <queue>
#define ll long long
#define DUNAJ '~'
#define EMO 'E'
#define KONTROLA 'K'
#define INTRAK 'I'
#define KONTROLA_JE_ZLA false
#define KONTROLA_JE_OK true
#define NEKONECNO 2000000047000000047LL
using namespace std;
// pair x-ovej, y-ovej suradnice a ceny
struct vec {
int surX, surY;
ll cena;
// nejake konstruktory, ktore nam ulahcia pracu s 'vec'
vec(int _surX, int _surY, ll _cena) : surX(_surX), surY(_surY), cena(_cena) {}
vec(pair<int, int> _surXY, ll _cena) : surX(_surXY.first), surY(_surXY.second), cena(_cena) {}
// aby halda usporaduvala od najnizsej .cena-y
bool operator< (const vec & dalsi) const {
return dalsi.cena < this->cena;
}
};
const char krizovatky[] = {'L', 'P', 'H', 'D'};
// vsimnite si, ze dx[] a dy[] koresponduju so smermi v krizovatky[]
const int dx[] = {0, 0, -1, 1}; // dx[i] je posunutie v x-ovej suradnici pri smere i
const int dy[] = {-1, 1, 0, 0}; // podobne dy predstavuje posunutie v y-ovej suradnici
// pokuty[i] = pokuta za porusenie prik. smeru krizovatky[i]
ll pokuty[] = {0LL, 0LL, 0LL, 0LL};
ll Po; // pokuta za ohnostroj
int r, s;
pair<int, int> E, I; // suradnice Ema a Intraku
vector< vector<char> > B; // mapa Bratislavy
ll cena(char policko, int smer) {
if (policko == krizovatky[smer])
return 0LL;
for(int i=0; i<4; ++i)
if (policko == krizovatky[i])
return pokuty[i];
return 0LL;
}
// dijkstra
ll spocitaj(bool flag) {
vector< vector<bool> > vis(r+2); // visited? aby som sa viac krat nepozeral na to iste
for(int i=0; i<r+2; ++i) vis[i].resize(s+2, false);
priority_queue< vec > PQ;
// Emo sa zatial nepohol a nic nezaplatil
PQ.push(vec(E, 0LL));
while (!PQ.empty()) {
vec p = PQ.top(); PQ.pop();
if (vis[p.surX][p.surY]) continue;
vis[p.surX][p.surY] = true;
if (B[p.surX][p.surY] == DUNAJ) continue;
if (flag == KONTROLA_JE_ZLA && B[p.surX][p.surY] == KONTROLA) continue;
// dosli sme uz do ciela? ak hej tak isto s najlepsou cenou
if (p.surX == I.first && p.surY == I.second)
return p.cena;
for(int i=0; i<4; ++i)
// od nasho policka ideme smerom i, teda x zvysime o dx[i] a y o dy[i]
// cenu zvysime o pokutu za tento smer, co nam urci funkcia cena ked
// jej hodime krizovatku na ktorej sme a smer ktorym chceme ist
PQ.push(vec(p.surX + dx[i],
p.surY + dy[i],
p.cena + cena(B[p.surX][p.surY], i)));
}
// ak sme tu, nevieme sa na intrak dostat
return NEKONECNO;
}
int main() {
// nacitavanie pokut a rozmerov mapy
cin >> Po;
for(int i=0; i<4; ++i) cin >> pokuty[i];
cin >> r >> s;
// mapu Bratislavy si zvacsime a inicializujeme na dunaj, cim pridame 'okraje'
B.resize(r+2); for(int i=0; i<r+2; ++i) B[i].resize(s+2, DUNAJ);
// postupne ju tam pridavame, predstavujeme si ju dokolecka obkolesenu dunajom
for(int i=1; i<r+1; ++i) for(int j=1; j<s+1; ++j) {
cin >> B[i][j];
// zapamatame si ak sme narazili na Ema alebo Intrak
if (B[i][j] == EMO)
E = {i, j};
else if (B[i][j] == INTRAK)
I = {i, j};
}
// Emo bud neprejde kontrolou alebo prejde niekolkymi a zaplati pokutu za ohnostroj
ll vysledok = min(spocitaj(KONTROLA_JE_ZLA), Po + spocitaj(KONTROLA_JE_OK));
// ak je vysledok nekonecno, riesenie neexistuje, inak vypisem na co som prisiel
cout << (vysledok < NEKONECNO ? vysledok : -1LL) << endl;
return 0;
}
Iný pohľad na kontroly
Rovnako rýchle riešenie je vytvoriť si 2 vrcholy pre každú križovatku. Jeden typ reprezentuje križovatky s tým, že sme na ceste k nim ešte žiadnou kontrolou neprešli a druhý reprezentuje, že sme už aspoň cez jednu kontrolu prešli. Keďže nevieme, či bude optimálne ísť cez kontroly, alebo nie, potrebujeme si pamätať oba vrcholy. V 3D sa to dá predstaviť ako keby sme urobili kópiu nášho grafu a položili ju nad náš graf. Takto dostaneme dvojúrovňový graf. Dolná úroveň sú vrcholy, ktoré hovoria, že sme ešte neprešli žiadnou kontrolou a horná úroveň sú vrcholy, ktoré hovoria, že už sme prešli aspoň jednou kontrolou. Vrcholy v rámci jednej úrovne budú pospájané hranami rovnakých cien, ako sme si popisovali (na oboch úrovniach). Jediná výnimka budú križovatky s kontrolami v dolnej úrovni. Ak sa dostaneme do križovatky s kontrolou v dolnej úrovni, tak potom pokračujeme v našej ceste v hornej úrovni. Za prechod medzi úrovňami zaplatíme cenu pokuty za ohňostroj. Ďalej už pokračujeme iba po hornej vrstve.
Na tomto grafe spočítame Dijkstrovým algoritmom najlacnejšiu cestu na lacnejší vrchol internátu. Zaujíma nás totiž tá lacnejšia z týchto dvoch najlacnejších ciest na jednotlivé vrcholy. Je nám jedno na akej úrovni grafu skončíme.
Ariadnina niť↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.