1275 - Jaina

Cerinta

Jaina se află în Theramore Isle și trebuie să ajungă la mentorul ei, Antonidas. Aceștia se află într-o matrice pătratică de dimensiune n x n, în poziții de coordonate cunoscute.

Jaina se poate deplasa în oricare dintre cele 8 direcții. Astfel, dacă inițial ea se găsește în celula de coordonate (x, y), poate ajunge în oricare dintre celulele (x-1, y-1), (x-1, y), (x-1, y + 1), (x, y + 1), (x + 1, y + 1), (x + 1, y), (x + 1, y - 1) sau (x, y - 1) făcând exact un pas.

În anumite celule se află câte o sursă de energie. Fiecare sursă emite raze în patru direcții (N, E, S, V), fiecare rază ajungând până la marginea matricei.

Când Jaina pășește pe o astfel de rază, ea se teleportează obligatoriu în celula sursei razei respective, deci nu este posibilă trecerea dincolo de aceste raze decât prin punctul sursă. Teleportarea este automată și instantanee și nu se consideră ca fiind un pas al Jainei.

Antonidas vă roagă să o ajutați pe Jaina să ajungă la el, efectuând un număr minim de pași!

Date de intrare

Fișierul de intrare jainaIN.txt conține pe prima linie numărul n, iar pe a doua linie 4 numere naturale separate prin spații, care semnifică coordonatele celulei în care se află Jaina și coordonatele celulei în care se află Antonidas. ( 2 perechi linie-coloană )

A treia linie conține numărul m de surse de energie.

Pe următoarele m linii se află câte două numere naturale x y, reprezentând coordonatele fiecărei surse.

Date de ieșire

Fișierul de ieșire jainaOUT.txt va conține pe prima linie numărul nrp, reprezentând numărul minim de pași pe care Jaina trebuie să-i efectueze pentru a ajunge la Antonidas. Î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 ≤ m ≤ 10
• Orice celulă are dimensiunea 1x1
• În cazul în care Jaina se află la intersecția a două raze de surse diferite, aceasta se va teleporta la sursa de linie minimă.
• Nu există două surse care să se afle pe aceeași linie sau pe aceeași coloană.
• Se garantează că există soluție pentru toate testele.
• Antonidas promite că o să fiți răsplătiți cu o minge de foc dacă găsiți răspunsul corect la această problemă.
• Deoarece Jaina este disperată, limitele de memorie sunt foarte mari, însă pe viitor nu este garantat acest lucru!

Exemplul 1:

jainaIN.txt

4
2 1 4 4 
1
3 3

jainaOUT.txt

2

Explicație

Numărul de pași necesari în acest caz este 2.

Exemplul 2:

jainaIN.txt

4
2 1 4 4 
1
3 3

jainaOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from collections import deque

class Celula:
    def __init__(self):
        self.val = 0
        self.laser = 0
        self.xs = 0
        self.ys = 0

nmax = 100
dl = [-1, -1, -1, 0, 1, 1, 1, 0]
dc = [-1, 0, 1, 1, 1, 0, -1, -1]

def inside(x, y, n):
    return 1 <= x <= n and 1 <= y <= n

def nord_sud(x, y, a, n):
    for i in range(1, n + 1):
        if a[i][y].laser == 0 and i != x:
            a[i][y].laser = 1
            a[i][y].xs = x
            a[i][y].ys = y
        elif i != x:
            if x < a[i][y].xs:
                a[i][y].xs = x
                a[i][y].ys = y

def est_vest(x, y, a, n):
    for j in range(1, n + 1):
        if a[x][j].laser == 0 and j != y:
            a[x][j].laser = 1
            a[x][j].xs = x
            a[x][j].ys = y
        elif j != y:
            if x < a[x][j].xs:
                a[x][j].xs = x
                a[x][j].ys = y

def solve(n, xi, yi, xf, yf, m, a):
    q = deque([(xi, yi)])
    a[xi][yi].val = 1

    while q:
        f1, f2 = q.popleft()

        for k in range(8):
            iv = f1 + dl[k]
            jv = f2 + dc[k]

            if inside(iv, jv, n) and (not a[iv][jv].val or a[iv][jv].val > a[f1][f2].val + 1):
                if a[iv][jv].laser == 0:
                    a[iv][jv].val = a[f1][f2].val + 1
                    q.append((iv, jv))
                else:
                    lin = a[iv][jv].xs
                    col = a[iv][jv].ys
                    a[iv][jv].val = a[f1][f2].val + 1

                    if a[lin][col].val > a[iv][jv].val or not a[lin][col].val:
                        a[lin][col].val = a[iv][jv].val
                        q.append((lin, col))
                        q.append((iv, jv))

    return a[xf][yf].val - 1

def verificare_restrictii(n, m):
    if not (1 <= n <= 100 and 1 <= m <= 10):
        with open("jainaOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

def citire():
    with open("jainaIN.txt", "r") as f:
        n = int(f.readline().strip())
        xi, yi, xf, yf = map(int, f.readline().split())
        m = int(f.readline().strip())
        if not verificare_restrictii(n, m):
            exit()  # Ieșire din program dacă restricțiile nu sunt respectate
        a = [[Celula() for _ in range(nmax + 1)] for _ in range(nmax + 1)]
        for _ in range(m):
            x, y = map(int, f.readline().split())
            nord_sud(x, y, a, n)
            est_vest(x, y, a, n)
    return n, xi, yi, xf, yf, a

def scriere(result):
    with open("jainaOUT.txt", "w") as f:
        f.write(str(result))

def main():
    n, xi, yi, xf, yf, a = citire()
    result = solve(n, xi, yi, xf, yf, n, a)
    scriere(result)

if __name__ == "__main__":
    main()