2163 - Episodul 3

Enunț

Zoli joacă cu un labirint de dimensiune N x N, format din camere de dimensiune 1 x 1, inițial toate inaccesibile. Auzind că Zoli este mare informatician, Dănutz și D’Umbră au decis să îl pună la încercare, după cum urmează:

1 x y: Dănutz transformă camera inaccesibilă (x, y) într-una accesibilă.

2 x1 y1 x2 y2: D’Umbră îl întreabă pe Zoli care este numărul minim de camere ce trebuie traversate pentru a ajunge din camera accesibilă (x1, y1) în camera accesibilă (x2, y2).

Cerința

Zoli a rezolvat deja această problemă, fiind una banală. El s-a dus să se joace LOL și este curios dacă o poți rezolva și tu. Pentru M evenimente de forma celor de mai sus, să se scrie un program care le procesează și afișează în fișierul de ieșire rezultatele operațiilor de tip 2, în ordinea în care acestea apar în fișierul de intrare.

Date de intrare

Fișierul de intrare episodul3IN.txt conține pe prima linie numerele N și M, iar pe următoarele M linii cele M operații.

Date de ieșire

Fișierul de ieșire episodul3OUT.txt va conține pe fiecare linie rezultatele operațiilor de tipul 2, în ordinea în care acestea apar în fișierul de intrare. Î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 ≤ 1000
• 1 ≤ M ≤ 250.000
• 1 ≤ x, y ≤ N
• pentru operațiile de tipul 1: camera (x, y) va avea exact o cameră vecină pe linie sau coloană deja accesibilă la momentul transformării sale, excepție făcând camera care este transformată prima.
• InParser
• OutParser

Exemplul 1:

episodul3IN.txt

5 7
1 1 1
1 1 2
2 1 1 1 2
1 2 2
1 1 3
2 1 3 2 2
2 1 1 2 2

episodul3OUT.txt

2
3
3

Exemplul 2:

episodul3IN.txt

1001 7
1 1 1
1 1 2
2 1 1 1 2
1 2 2
1 1 3
2 1 3 2 2
2 1 1 2 2

episodul3OUT.txt

2
3
3

Rezolvare

class InParser:
    def __init__(self, filename):
        self.fin = open(filename, "r")
        self.buff = self.fin.read()
        self.sp = -1
        self.length = len(self.buff)

    def read_ch(self):
        self.sp += 1
        if self.sp < self.length:
            return self.buff[self.sp]
        return ''

    def __lshift__(self, n):
        c = self.read_ch()
        while c and not c.isdigit() and c != '-':
            c = self.read_ch()
        if not c:
            return self
        sgn = 1
        if c == '-':
            n[0] = 0
            sgn = -1
        else:
            n[0] = int(c)
        c = self.read_ch()
        while c.isdigit():
            n[0] = 10 * n[0] + int(c)
            c = self.read_ch()
        n[0] *= sgn
        return self

class OutParser:
    def __init__(self, filename):
        self.fout = open(filename, "w")
        self.buff = []
        self.sp = 0

    def __del__(self):
        self.fout.write("".join(self.buff))
        self.fout.close()

    def __lshift__(self, vu32):
        if isinstance(vu32, int):
            self.buff.append(str(vu32))
        elif isinstance(vu32, str):
            self.buff.append(vu32)
        return self

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
Nmax = 1005
getNode = [[0] * Nmax for _ in range(Nmax)]
T = [[0] * (Nmax * Nmax) for _ in range(22)]
nodes = 0
dist = [0] * (Nmax * Nmax)

def getKthAncestor(K, node):
    for i in range(10, -1, -1):
        if K & (1 << i):
            node = T[i][node]
            K -= (1 << i)
    return node

def getLCA(node1, node2):
    if node1 == node2:
        return node1
    pos = dist[node1] + 1
    i = 0
    while (1 << i) <= dist[node1]:
        i += 1
    for i in range(i, -1, -1):
        if T[i][node1] != T[i][node2]:
            node1 = T[i][node1]
            node2 = T[i][node2]
            pos -= (1 << i)
    return T[0][node1]

def main():
    fin = InParser("episodul3IN.txt")
    fout = OutParser("episodul3OUT.txt")

    N = [0]
    M = [0]
    fin << N << M
    N = N[0]
    M = M[0]

    if not (1 <= N <= 1000) or not (1 <= M <= 250000):
        fout << "Datele nu corespund restrictiilor impuse"
        return

    global nodes
    for _ in range(M):
        t = [0]
        fin << t
        t = t[0]
        if t == 1:
            i = [0]
            j = [0]
            fin << i << j
            i = i[0]
            j = j[0]
            if not (1 <= i <= N and 1 <= j <= N):
                fout << "Datele nu corespund restrictiilor impuse"
                return
            nodes += 1
            getNode[i][j] = nodes
            for d in range(4):
                ni = i + dx[d]
                nj = j + dy[d]
                if getNode[ni][nj] != 0:
                    T[0][nodes] = getNode[ni][nj]
                    dist[nodes] = 1 + dist[getNode[ni][nj]]
            if dist[nodes] == 0:
                dist[nodes] = 1
            for i in range(1, 22):
                if (1 << i) <= dist[nodes]:
                    T[i][nodes] = T[i - 1][T[i - 1][nodes]]
        elif t == 2:
            i = [0]
            j = [0]
            i2 = [0]
            j2 = [0]
            fin << i << j << i2 << j2
            i = i[0]
            j = j[0]
            i2 = i2[0]
            j2 = j2[0]
            if not (1 <= i <= N and 1 <= j <= N and 1 <= i2 <= N and 1 <= j2 <= N):
                fout << "Datele nu corespund restrictiilor impuse"
                return
            node1 = getNode[i][j]
            node2 = getNode[i2][j2]
            if dist[node1] > dist[node2]:
                node1, node2 = node2, node1
            sameLevel = getKthAncestor(dist[node2] - dist[node1], node2)
            LCA = getLCA(node1, sameLevel)
            fout << dist[node1] + dist[node2] - 2 * dist[LCA] + 1 << "\n"

if __name__ == "__main__":
    main()