#include // Autorské řešení úlohy 26-2-3: Plánování cesty // Verze využívající průchod do šířky, časová složitost // je O(M*R*S), kde R x S jsou rozměry terénu a M maximální // potřebný čas pro překonání jednoho políčka. // Pro překlad je nutno použít jazyk C v normě C99 nebo novější. #define MAX 1000 #define MAXQ (MAX*MAX) int R, S; // Rozměry oblasti 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á jednak souřadnice r, s. // V proměnné t pak udává, kolikrát je potřeba políčko // ještě zařadit do fronty, než bude zpracováno. struct P { int r, s, t; }; // 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 int V[MAX][MAX]; // Fronta políček Q // Q_zac, Q_kon označují pozice aktuálního začátku/konce fronty // Políčka vkládáme na konec fronty a vybíráme je ze začátku struct P Q[MAXQ]; int Q_zac, Q_kon; // Zařadíme políčko p do fronty // Nesmíme zapomenout ošetřit přetečení fronty void vloz(struct P p) { Q[Q_kon] = p; Q_kon = Q_kon == MAXQ - 1 ? 0 : Q_kon + 1; } // Vyjmeme políčko ze začátku fronty // Nesmíme zapomenout ošetřit přetečení fronty struct P vyjmi() { int puvodni_zac = Q_zac; Q_zac = Q_zac == MAXQ - 1 ? 0 : Q_zac + 1; return Q[puvodni_zac]; } // Pro políčko (r,s) zpracujeme souseda (S_r,S_s) // To znamená nejprve ověřit, zda jsou vůbec jeho souřadnice korektní. // V případě, že ještě nebyl zpracován a lze na něj vstoupit, // jej zařadíme do fronty. 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 (V[S_r][S_s] == -1 && T[S_r][S_s] != 0) { V[S_r][S_s] = V[r][s] + T[r][s]; vloz((struct P){ .r = S_r, .s = S_s, .t = T[S_r][S_s] - 1}); } } } 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, .t = 0 }); V[R_odkud][S_odkud] = 0; // Zpracováváme políčka fronty, dokud nějaká obsahuje while (Q_kon != Q_zac) { struct P p = vyjmi(); if (p.s == S_kam && p.r == R_kam) { // Už jsme našli cíl a nemá smysl se dál zdržovat break; } if (p.t != 0) { p.t--; vloz(p); } else { 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("%d\n", V[R_kam][S_kam]); return 0; }