Editing 1337 - Susan

== Cerinta == 

Eroul nostru Susan se află într-un turn de formă cubică, de latură <code>n</code>. 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 <code>n</code> etaje, iar fiecare etaj este împărțit în <code>n x n</code> 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 <code>turnIN.txt</code> conține:

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

= Date de ieșire =
Fișierul de ieșire <code>turnOUT.txt</code> va conține numărul minim de pași pe care îl poate face Susan pentru a ajunge la comoara sa. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ z ≤ 30000</code>
* <code>1 ≤ s1 ≤ s2 ≤ 200</code>
* <code>1 ≤ g ≤ 10000</code>
* 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: =
<code>turnIN.txt</code>
 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
<code>turnOUT.txt</code>
 11

== Explicație ==
Turnul are <code>3</code> etaje. Susan pleacă din celula de coordonate <code>(1 1 1)</code>, iar celula în care se află comoara are coordonatele <code>(2 2 1)</code>. Există <code>9</code> celule în care se află ziduri, <code>3</code> celule în care se află scări ascendente, <code>3</code> celule în care se află scări descendente și <code>3</code> celule în care se află gropi. Traseul cel mai scurt trece prin <code>11</code> camere: <code>(1 1 1) (1 1 2) (1 2 2) (1 2 3) (2 2 3) (2 3 3) (2 3 2) (3 3 2) (3 2 2) (3 2 1) (2 2 1)</code>.

== Exemplul 2: ==
<code>turnIN.txt</code>
 101
 9 3 3 3
 1 1 3
 1 2 1
 1 3 2
<code>turnOUT.txt</code>
 Datele nu corespund restrictiilor impuse
:

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
from collections import deque

dy = [1, -1, 0, 0]
dz = [0, 0, 1, -1]

def inmat(i, j, k, n):
    return 1 <= i <= n and 1 <= j <= n and 1 <= k <= n

def lee(n, a, is_, js, ks, ifi, jfi, kfi):
    b = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
    q = deque([(is_, js, ks)])
    b[is_][js][ks] = 1

    while q:
        x, y, w = q.popleft()
        if a[x][y][w] != 4:
            for d in range(4):
                ii = x
                jj = y + dy[d]
                kk = w + dz[d]
                if inmat(ii, jj, kk, n) and a[ii][jj][kk] != 1 and b[ii][jj][kk] == 0:
                    b[ii][jj][kk] = b[x][y][w] + 1
                    q.append((ii, jj, kk))
        if a[x][y][w] == 4:
            ii = x
            cnt = 0
            while a[ii][y][w] == 4:
                ii -= 1
                cnt += 1
            if inmat(ii, y, w, n) and a[ii][y][w] != 1 and b[ii][y][w] == 0:
                b[ii][y][w] = b[x][y][w] + cnt
                q.append((ii, y, w))
        elif a[x][y][w] == 3:
            ii = x - 1
            if inmat(ii, y, w, n) and a[ii][y][w] != 1 and b[ii][y][w] == 0:
                b[ii][y][w] = b[x][y][w] + 1
                q.append((ii, y, w))
        elif a[x][y][w] == 2:
            ii = x + 1
            if inmat(ii, y, w, n) and a[ii][y][w] != 1 and b[ii][y][w] == 0:
                b[ii][y][w] = b[x][y][w] + 1
                q.append((ii, y, w))

    return b[ifi][jfi][kfi]

def verificare_restrictii(n, z, sa, sd, g):
    if not (1 <= n <= 100 and 1 <= z <= 30000 and 1 <= sa <= sd <= 200 and 1 <= g <= 10000):
        with open("turnOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

with open("turnIN.txt", "r") as f:
    n = int(f.readline().strip())
    z, sa, sd, g = map(int, f.readline().split())
    if not verificare_restrictii(n, z, sa, sd, g):
        exit()

    a = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(z):
        x, y, w = map(int, f.readline().split())
        a[x][y][w] = 1
    for _ in range(sa):
        x, y, w = map(int, f.readline().split())
        a[x][y][w] = 2
    for _ in range(sd):
        x, y, w = map(int, f.readline().split())
        a[x][y][w] = 3
    for _ in range(g):
        x, y, w = map(int, f.readline().split())
        a[x][y][w] = 4
    is_, js, ks = map(int, f.readline().split())
    ifi, jfi, kfi = map(int, f.readline().split())

result = lee(n, a, is_, js, ks, ifi, jfi, kfi)

with open("turnOUT.txt", "w") as f:
    if result is not None:
        f.write(str(result))

</syntaxhighlight>