Editing 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 ==

<syntaxhighlight lang="python3" line="1">

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>