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 turnIN.txt 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 ieșire

Fișierul de ieșire turnOUT.txt 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

• 1 ≤ 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

11

Explicație

Turnul are 3 etaje. Susan pleacă din celula de coordonate (1 1 1), iar celula în care se află comoara are coordonatele (2 2 1). Există 9 celule în care se află ziduri, 3 celule în care se află scări ascendente, 3 celule în care se află scări descendente și 3 celule în care se află gropi. Traseul cel mai scurt trece prin 11 camere: (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).

Exemplul 2:

turnIN.txt

101
9 3 3 3
1 1 3
1 2 1
1 3 2

turnOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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))