1337 - Susan

Cerinta

Eroul nostru Susan se află într-un turn de formă cubică, de latură n. El dorește să ajungă la comoara ascunsă în interiorul turnului. Din fericire, Susan a făcut rost de o hartă care îi indică cu exactitate coordonatele locului în care se află comoara din turn. Eroul nostru vrea să știe care este distanța minimă pe care o poate parcurge pentru a ajunge la comoară.

Turnul este împărțit în n etaje, iar fiecare etaj este împărțit în n x n celule (camere). O cameră poate:

fi blocată, astfel fiind inaccesibilă eroului nostru
fi accesibilă, astfel eroul nostru poate intra în aceasta
conține o scară ascendentă care îl poate duce pe erou cu un etaj mai sus, în camera situată deasupra camerei curente
conține o scară descendentă care îl poate duce pe erou cu un etaj mai jos, în camera situată sub camera curentă
conține o trapă prin care eroul va cădea la etajul inferior, în camerele situate sub camera curentă (dacă eroul, în urma căderii, se află într-o cameră ce conține o trapă, el va continua *să cadă până se va afla într-o o cameră fără trapă, pe aceeași coloană)

La fiecare trecere dintr-o cameră în alta, eroul execută un pas.

Fiind date latura turnului și coordonatele zidurilor, scărilor, gropilor, eroului și a comorii, se cere să se afișeze numărul minim de pași pe care îl poate parcurge Susan pentru a ajunge la comoară.

Date de intrare

Fișierul de intrare turn.in conține:

pe prima linie numărul n, reprezentând lungimea laturii turnului.
pe a doua linie se află numărul z, reprezentând numărul de ziduri, numărul s1, reprezentând numărul de scări descendente, numărul s2, reprezentând numărul de scări descendente și numărul g, reprezentând numărul de gropi.
pe următoarele z linii se află coordonatele zidurilor.
pe următoarele s1 linii se află coordonatele scărilor ascendente.
pe următoarele s2 linii se află coordonatele scărilor descendente.
pe următoarele g linii se află coordonatele gropilor.
pe penultima linie se află coordonatele eroului, iar pe ultima linie se află coordonatele comorii.

Date de iesire

Fișierul de ieșire turn.out va conține numărul minim de pași pe care îl poate face Susan pentru a ajunge la comoara sa.

Restricții și precizări

≤ n ≤ 100
1 ≤ z ≤ 30000
1 ≤ s1 ≤ s2 ≤ 200
1 ≤ g ≤ 10000
Se garantează că există soluție pentru toate datele de test.
Poziția inițială se consideră a fi situată la pasul 1.
Trapa generează o cădere a eroului pe verticală, până când ajunge într-o cameră fără trapă.

Exemplul 1

turnin.txt

3

9 3 3 3

1 1 3

1 2 1

1 3 2

2 1 1

2 1 3

2 2 2

3 1 1

3 2 3

3 3 3

1 2 3

2 3 2

2 1 2

2 2 3

3 3 2

3 1 2

3 3 1

3 2 1

2 3 1

1 1 1

2 2 1

turnout.txt

Datele introduse corespund restrictiilor impuse.

11

Exemplul 2

trunin.txt

0

10 22 32 16

-1 -2 -3

-3 -1 -2

0 0 0

-2 -3 -1

-1 -2 -1

-3 -2 -2

-2 -2 -2

-3 -2 -1

-1 -2 -2

-3 -3 -1

-3 -2 -3

-2 -3 -1

-1 -1 -1

-2 -2 -1

-1 -3 -2

-3 -3 -2

turnout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

from collections import deque

def distanta_minima(latura_turn, coordonate_camere, coordonate_comoara):

   n = latura_turn
   turn = [[0] * n for _ in range(n)]

   for coord in coordonate_camere:
       x, y = coord
       turn[x][y] = 1  # Camera blocată

   sx, sy = coordonate_comoara[0]
   ex, ey = coordonate_comoara[1]

   # Coordonatele deplasării posibile
   deplasare = [(0, 1), (0, -1), (1, 0), (-1, 0)]

   # Coordonatele camerelor accesibile
   camere_accesibile = set()

   # Construim graful turnului
   for i in range(n):
       for j in range(n):
           if turn[i][j] == 0:
               camere_accesibile.add((i, j))

   # Funcția de verificare a validității unei camere
   def este_valida(x, y):
       return 0 <= x < n and 0 <= y < n and (x, y) in camere_accesibile

   # Algoritmul BFS pentru a găsi distanța minimă
   def bfs(start, scop):
       queue = deque([(start, 0)])  # Coada pentru BFS
       vizitat = set([start])  # Set pentru a urmări camerele vizitate

       while queue:
           (x, y), pasi = queue.popleft()

           if (x, y) == scop:
               return pasi  # Am ajuns la comoară

           for dx, dy in deplasare:
               nx, ny = x + dx, y + dy

               if este_valida(nx, ny) and (nx, ny) not in vizitat:
                   queue.append(((nx, ny), pasi + 1))
                   vizitat.add((nx, ny))

       return -1  # Comoara nu poate fi atinsă

   rezultat = bfs((sx, sy), (ex, ey))
   return rezultat

rezultat = distanta_minima(latura_turn, camere_blocare, coordonate_comoara) print(f"Numărul minim de pași necesari: {rezultat}")

</syntaxhighlight>