The End Dimension (Həll təhlili)

Həll

Müşahidələr:

• Maneələrdən keçmədən bir-birinə bağlı olan hüceyrələr əlaqəli komponentlər əmələ gətirir. Əgər başlanğıc və hədəf eyni komponentdədirsə, teleportasiya lazım deyil.

• Bir teleportasiya cihazından artıq istifadə etmək heç vaxt optimal deyil.

Alqoritm:

1. Bütün əlaqəli komponentləri DFS/BFS ilə işarələ.

2. Hansı komponentlərdə teleportasiya cihazı olduğunu qeyd et.

3. Bütün teleportasiya cihazlarından eyni anda BFS başladaraq hər $(i,j)$ üçün ən yaxın cihazadək məsafəni $d[i][j]$ hesabla.

4. Hər sorğu (x,y,b,c) üçün:

   • Əgər $(x,y)$ və $(b,c)$ eyni komponentdədirsə, cavab $=0$.

   • Əks halda, əgər hər ikisi teleportasiya cihazı olan komponentdədirsə, cavab $d[b][c]$.

   • Əks halda, çatmaq mümkün deyil, cavab $=-1$.

Ümumi mürəkkəblik: \mathcal{O}(n \cdot m + q).