2041 - Camelot

Cerința

Regele Arthur – Inimă de Leu, vrea să adune la castel toţi cavalerii Mesei Rotunde pentru a hotărî împreună soarta regatului. Dar cavalerii nu se află toţi în Camelot şi durează un timp până vor ajunge la castel din pădurea care înconjoară castelul.

Harta pădurii are forma unei matrici, cu m linii şi n coloane. Pentru fiecare cavaler care nu este în Camelot se cunosc coordonatele x y, reprezentând linia şi coloana din matrice în care se află iniţial cavalerul. Toţi cavalerii pornesc simultan spre castel, iar fiecare cavaler se deplasează după regula de deplasare a calului de la jocul de şah.

Cunoscând dimensiunile mxn ale matricei, coordonatele castelului şi cele ale cavalerilor, se cere să se determine:

1. numărul minim de mutări după care va ajunge la castel unul dintre cavaleri

2. numărul minim de mutări după care toţi cavalerii se vor afla la castel.

De exemplu, în imaginea de mai sus este reprezentată harta sub forma unei matrici de tip 8x8, iar castelul are coordonatele 4 5 (linia 4 şi coloana 5), primul cavaler se află iniţial în punctul de coordonate 1 2 iar cel de al doilea în punctul 8 1. Primul cavaler va ajunge la castel din minim 2 deplasări, iar al doilea după minim 4 mutări Pentru prima întrebare răspunsul este 2, iar pentru a doua întrebare răspunsul este 4.

Date de intrare

Fișierul de intrare camelotIN.txt conține pe prima linie numărul p, pentru toate testele de intrare numărul p putând avea doar valoarea 1 sau valoarea 2.

Pe cea de a doua linie sunt scrise numerele naturale m n k, separate prin câte un spaţiu, iar pe a treia linie se află coordonatele xc yc ale castelului. Pe următoarele k linii se află k perechi de numere întregi x[i] y[i] (1 ≤ i ≤ k), separate prin câte un spaţiu, reprezentând coordonatele cavalerilor.

Date de ieșire

Fișierul de ieșire camelotOUT.txt va conține pe prima linie:

• pentru p=1, pe prima linie se va scrie numărul minim de mutări după care va ajunge unul din cavaleri
• pentru p=2, pe prima linie se va scrie numărul minim de mutări după care vor ajunge toţi cavalerii. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 5 ≤ m,n ≤ 1000
• 1 ≤ k ≤ 1000
• 1 ≤ x[i], xc ≤ m, 1 ≤ y[i], yc ≤ n, pentru orice 1 ≤ i ≤ k
• Eventualele intersecţii ale drumurilor cavalerilor nu influenţează rezultatele
• Pentru datele de test se garantează existenţa unei soluţii

Exemplul 1:

camelotIN.txt

1
8 8 2
4 5
1 2
8 1

camelotOUT.txt

2

Exemplul 2:

camelotIN.txt

1
1001 8 2
4 5
1 2
8 1

camelotOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from collections import deque

dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [1, -1, -2, 2, -2, 2, -1, 1]

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

def check_restrictions(n, m, k, c1, c2, positions):
    if not (5 <= n <= 1000 and 5 <= m <= 1000):
        return "Datele nu corespund restrictiilor impuse"
    if not (1 <= k <= 1000):
        return "Datele nu corespund restrictiilor impuse"
    if not (1 <= c1 <= m and 1 <= c2 <= n):
        return "Datele nu corespund restrictiilor impuse"
    for x, y in positions:
        if not (1 <= x <= m and 1 <= y <= n):
            return "Datele nu corespund restrictiilor impuse"
    return None

def lee(ir, jr, n, m, b, q):
    b[ir][jr] = 1
    q.append((ir, jr))
    
    while q:
        x, y = q.popleft()
        for d in range(8):
            ii, jj = x + dx[d], y + dy[d]
            if inmat(ii, jj, n, m) and b[ii][jj] == 0:
                b[ii][jj] = b[x][y] + 1
                q.append((ii, jj))

if __name__ == "__main__":
    with open("camelotIN.txt", "r") as fin, open("camelotOUT.txt", "w") as fout:
        op = int(fin.readline().strip())
        n, m, k = map(int, fin.readline().strip().split())
        c1, c2 = map(int, fin.readline().strip().split())
        
        positions = [tuple(map(int, fin.readline().strip().split())) for _ in range(k)]
        
        restriction_error = check_restrictions(n, m, k, c1, c2, positions)
        if restriction_error:
            fout.write(restriction_error)
        else:
            a = [[0] * 1001 for _ in range(1001)]
            b = [[0] * 1001 for _ in range(1001)]
            q = deque()
            
            lee(c1, c2, n, m, b, q)
            
            mini = float('inf')
            maxi = 0
            
            for x, y in positions:
                if b[x][y] < mini:
                    mini = b[x][y]
                if b[x][y] > maxi:
                    maxi = b[x][y]
            
            if op == 1:
                fout.write(str(mini - 1))
            else:
                fout.write(str(maxi - 1))