4. Zakázané ohňostroje vzorové riešenie

10 10 1 6 4
4 3
HLL
IPK
D~H
DLE

8

1 2 3 4 5
2 2
E~
~I

-1

1000 1 2 3 4
4 6
DHHHPK
LELKHK
~P~PKL
PKLHI~

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íme¹. 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.