#include #include // Autorské řešení úlohy 26-2-3: Plánování cesty // Verze využívající Dijkstrův algoritmus, časová složitost // je O(RS * log RS), kde R x S jsou rozměry bludiště. // Pro překlad je nutno použít jazyk C v normě C99 nebo novější. #define MAX 1000 #define MAXH (MAX*MAX) int R, S; // Rozměry bludiště int R_odkud, S_odkud; // Souřadnice výchozího políčko int R_kam, S_kam; // Souřadnice cílového políčka // Označením (r,s) rozumíme políčko na r-tém řádku a s-tém sloupci // oblasti. Číslujeme od nuly. // Struktura pro jedno políčko bludiště // Udává jeho souřadnice r, s struct P { int r, s; }; // T[r][s] udává dobu potřebnou pro přechod políčka (r,s) // 0 znamená, že přechod je nemožný int T[MAX][MAX]; // V[r][s] udává nejkratší dobu, za kterou se lze dostat z počátečního // políčka na políčko (r,s) // -1 znamená, že tuto dobu neznáme nebo že se na (r,s) nelze // vůbec dostat long long V[MAX][MAX]; bool def[MAX][MAX]; // je (r,s) definitivní? // Halda H o N prvcích // Prvky haldy se nachází na pozicích 0,...,N-1 // Levý syn prvku q je 2*q + 1, pravý syn 2*q + 2 struct P H[MAXH]; int N; // I[r][s] udává pozici (r,s) v haldě int I[MAX][MAX]; bool mensi(struct P a, struct P b) { return V[a.r][a.s] < V[b.r][b.s]; } // Prohodíme prvky haldy na pozicích k a l void prohod(int k, int l) { I[H[k].r][H[k].s] = l; I[H[l].r][H[l].s] = k; struct P tmp = H[k]; H[k] = H[l]; H[l] = tmp; } void bublej_dolu(int q) { // Dokud jsme se neprobublali na poslední vrstvu while (2*q + 1 < N) { int min = 2*q + 1; if (2*q + 2 < N && mensi(H[2*q + 2], H[min])) min = 2*q + 2; if (mensi(H[min], H[q])) { prohod(q, min); q = min; } else break; } } void bublej_nahoru(int q) { while (q > 0 && mensi(H[q], H[(q-1)/2]) ) { prohod(q, (q-1)/2); q = (q-1) / 2; } } // Vložíme prvek na poslední pozici v haldě a následně // jej necháme probublat na správné místo void vloz(struct P p) { H[N] = p; I[p.r][p.s] = N; N++; bublej_nahoru(N-1); } // Minimem haldy je prvek na pozici 0 // Po jeho odebrání na tuto pozici vložíme poslední prvek, // který necháme probublat na správnou pozici. struct P vyjmi_minimum() { struct P vysledek = H[0]; prohod(0, N-1); N--; bublej_dolu(0); return vysledek; } // Pro políčko (r,s) zpracujeme souseda (S_r,S_s). // To znamená nejprve ověřit, zda jsou vůbec jeho souřadnice korektní. // Dále zjistíme, zda jsme nenalezli kratší cestu k němu. // Souseda pak případně v haldě přesuneme, nebo jej vložíme, pokud se // v ní ještě nenachází. void zpracuj_souseda(int r, int s, int S_r, int S_s) { if (S_r >= 0 && S_r < R && S_s >= 0 && S_s < S) { if (T[S_r][S_s] != 0 && (V[S_r][S_s] == -1 || V[r][s] + T[r][s] < V[S_r][S_s]) ) { bool je_v_halde = V[S_r][S_s] != -1; V[S_r][S_s] = V[r][s] + T[r][s]; if (je_v_halde) { bublej_nahoru(I[S_r][S_s]); } else vloz((struct P){ .r = S_r, .s = S_s }); } } } int main() { scanf("%d%d", &R, &S); scanf("%d%d", &R_odkud, &S_odkud); scanf("%d%d", &R_kam, &S_kam); for (int r = 0; r < R; r++) { for (int s = 0; s < S; s++) { V[r][s] = -1; scanf("%d", &T[r][s]); } } vloz((struct P){ .r = R_odkud, .s = S_odkud }); V[R_odkud][S_odkud] = 0; def[R_odkud][S_odkud] = true; // Zpracováváme políčka haldy, dokud nějaká obsahuje while (N > 0) { struct P p = vyjmi_minimum(); if (p.r == R_kam && p.s == S_kam) { // Už jsme našli cíl a nemá smysl se dál zdržovat break; } int r = p.r, s = p.s; zpracuj_souseda(r, s, r-1, s); zpracuj_souseda(r, s, r+1, s); zpracuj_souseda(r, s, r, s-1); zpracuj_souseda(r, s, r, s+1); } printf("%lld\n", V[R_kam][S_kam]); return 0; }