U popularnoj igri “Zmije i lestve” igrač se kreće od početnog polja bacajući kockicu i pomerajući se onoliko polja unapred koliko pokaže kockica. Postoje dve vrste posebnih polja. Ako igrač stane na neko polje na kom se nalaze “lestve”, on se penje uz te lestve i prelazi na ono polje sa većim brojem do koga te lestve vode. Ako igrač stane na neko polje na kom se nalazi zmija, on se spušta i prelazi na ono polje sa manjim brojem do koga ta zmija vodi. Napisati program koji određuje minimalan broj koraka (bacanja kockice) kojima igrač može da stigne od početnog do završnog polja.
Napomena: Ako igrač stigne na neko polje koje je deo ciklusa sastavljenog od lestvi i zmija, on momentalno gubi igru i ne može da stigne do cilja (takva polja se moraju izbegavati).
Sa standardnog ulaza se učitava ukupan broj polja \(n\) (\(5 \leq n \leq 200\)). Polja su obeležena brojevima od 0 do \(n-1\). U narednom redu se nalazi najveći broj \(k\) koji se može dobiti bacanjem kockice (kockicom se dobijaju brojevi od \(1\) do \(k\)). Nakon toga se učitava ukupan broj \(m\) zmija i lestvi (\(0 \leq m \leq n\)), a zatim i podaci o njima (broj polaznog i broj dolaznog polja).
Na standardni izlaz ispisati traženi minimalni broj koraka. Ako nije moguće stići do cilja, ispisati -1.
18 2 5 2 12 3 13 8 17 11 1 14 7
3
Dobijanjem broja 2, igrač sa polja 0 prelazi na polje 2 i zatim se lestvama penje do polja 12. Dobijanjem broja 2, dolazi na polje 14, odakle se zmijom spušta do polja 7. Dobijanjem broja 1, dolazi na polje 8, odakle se lestvama penje do ciljnog polja 17.
5 2 2 1 3 3 1
2
Igrač ne sme da stane na polje 1 ili 3, jer će tada izgubiti zbog ciklusa na kom se nalazi. Zato mu je najbolje da prvo dođe do polja 2, pa zatim do polja 4.
Problem se može modelovati grafom na nekoliko načina. Jedan način je da čvorovi grafa budu polja na tabli, a da grane budu prelazi između polja (za svako polje pamtimo spisak polja do kojih možemo stići nakon bacanja kockice i iscrpnog praćenja svih lestvi i zmija (nema potrebe praviti razliku između njih). Prilikom određivanja grana takvog grafa, za svako polazno polje \(p\) određujemo sve moguće ishode bacanja kockice i za svaki ishod kockice od polja \(p+i\) pratimo iscrpno lestve i zmije dok god je to moguće ili dok ne ustanovimo da smo upali u ciklus (tako što smo se ponovo vratili na polje \(p+i\)). Ako nismo upali u ciklus i stigli smo do nekog polja \(c\) od kojeg dalje ne vode lestve niti zmije, u graf dodajemo granu od \(p\) do \(c\).
Pošto se traži najmanji broj koraka da se stigne od početnog do krajnjeg čvora prirodno je primeniti klasičnu pretragu u širinu nad ovako formiranim grafom. Za svako polje pamtimo i broj koraka koji je bio potreban da se do njega stigne. Pretraga u širinu se završava kada prvi put odredimo broj koraka potrebnih da stignemo do polja \(n-1\).
#include <iostream>
#include <map>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
int k;
cin >> k;
// učitavamo zmilje i lestve
int m;
map<int, int> prelaz;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
prelaz[a] = b;
}
// kreiramo graf
vector<vector<int>> graf(n);
for (int polje = 0; polje < n; polje++) {
if (prelaz.find(polje) != prelaz.end())
continue;
for (int i = 1; i <= k && polje + i < n; i++) {
// pomeramo se za i polja
int cilj = polje + i;
// sa tog polja pratimo lestve i zmije dok je god moguće, vodeći
// računa o tome da ne upadnemo u ciklus
bool ciklus = false;
while (true) {
auto it = prelaz.find(cilj);
if (it == prelaz.end())
break;
cilj = it->second;
if (cilj == polje + i) {
ciklus = true;
break;
}
}
// ako smo uspešno stigli na neko krajnje polje, dodajemo prelaz u graf
if (!ciklus)
graf[polje].push_back(cilj);
}
}
// broj koraka potreban da se stigne do svakog polja (-1 znači da je taj
// broj trenutno nepoznat)
vector<int> rastojanje(n, -1);
// pretraga u širinu
queue<int> red;
red.push(0);
rastojanje[0] = 0;
while (!red.empty()) {
int polje = red.front();
red.pop();
for (int cilj : graf[polje])
if (rastojanje[cilj] == -1) {
rastojanje[cilj] = rastojanje[polje] + 1;
red.push(cilj);
// prvi put kada stignemo do cilja prekidamo pretragu
if (polje == n-1)
break;
}
}
cout << rastojanje[n-1] << endl;
return 0;
}Problem možemo predstaviti grafom tako da čvorovi grafa budu polja na tabli, a grane lestve tj. zmije (nema potrebe praviti razliku između njih).
Pošto se traži najmanji broj koraka da se stigne od početnog do krajnjeg čvora prirodno je primeniti pretragu u širinu, međutim, pošto graf ovaj put predstavlja lestve i zmije, a ne konačne prelaze, ta pretraga se mora malo prilagoditi.
Od svakog polja \(p\) bacanjem kockice možemo stići na polja \(p+1\), \(p+2\), \(\ldots\), \(p+k\) (ti prelazi nisu eksplicitno predstavljeni grafom, ali su implicitno određeni). Kada stignemo na neko polje \(p+i\), pratimo iscrpno lestve i zmije sve dok je moguće ili dok ne ustanovimo da smo napravili ciklus (tako što se ponovo vratimo na polje \(p+i\)). Ako nismo napravili ciklus sa polja \(p\) vršimo prelaz na polje \(c\) koje je bilo poslednje dostupno lestvama i zmijama i od kojeg dalje ne vode lestve niti zmije (dakle, ne prelazimo na polje \(p+i\), već na polje \(c\)). Za svako polje pamtimo i broj koraka koji je bio potreban da se do njega stigne. Pretraga u širinu se završava kada prvi put odredimo broj koraka potrebnih da stignemo do polja \(n-1\).
#include <iostream>
#include <map>
#include <queue>
using namespace std;
class Graph {
private:
int number_of_nodes;
int dice_max_step;
// Mapa koja govori s kog na koje current_field se moze preci zmijom ili lestvom
map<int, int> snakes_and_ladders;
public:
Graph(int number_of_nodes, int dice_max_step) {
this->number_of_nodes = number_of_nodes;
this->dice_max_step = dice_max_step;
}
void add_snake_or_ladder(int start_field, int end_field) {
snakes_and_ladders[start_field] = end_field;
}
int find_shortest_path() {
// Udaljenost od pocetnog polja do svih drugih polja, inicijalno -1 za sva polja
vector<int> distances(number_of_nodes, -1);
queue<int> q;
q.push(0);
distances[0] = 0;
while (!q.empty()) {
int current_field = q.front();
q.pop();
// Idemo kroz sve implicitno dodate grane jer znamo da od svakog polja mozemo da skocimo na bilo koje od narednih dice_max_step polja
for (int i = 1; i <= dice_max_step && current_field + i < number_of_nodes; i++) {
int next_field = current_field + i;
bool snake_ladder_cycle = false;
while (true) {
// Pokusavamo od trenutnog polja da krenemo zmijama ili lestvama cime ne pravimo dodatna bacanja kockice
auto it = snakes_and_ladders.find(next_field);
if (it == snakes_and_ladders.end()) {
break;
}
next_field = it->second;
// Ako se vratimo u polje iz kog smo krenuli imamo ciklus zmija i lestvi
if (next_field == current_field + i) {
snake_ladder_cycle = true;
break;
}
}
// Ako nismo upali u ciklus i ako do sada nismo posetili polje, ono je zanimljivo i zelimo da i to polje
// razmatramo pa ga dodajemo u red
if (!snake_ladder_cycle && distances[next_field] == -1) {
distances[next_field] = distances[current_field] + 1;
q.push(next_field);
if (next_field == number_of_nodes-1)
break;
}
}
}
return distances[number_of_nodes-1];
}
};
int main() {
int number_of_nodes, dice_max_step;
cin >> number_of_nodes >> dice_max_step;
int number_of_snakes_and_ladders;
cin >> number_of_snakes_and_ladders;
Graph *G = new Graph(number_of_nodes, dice_max_step);
int start_field, end_field;
for (int i = 0; i < number_of_snakes_and_ladders; i++) {
cin >> start_field >> end_field;
G->add_snake_or_ladder(start_field, end_field);
}
cout << G->find_shortest_path() << "\n";
delete G;
return 0;
}