Editing 2163 - Episodul 3

= Enunț =
Zoli joacă cu un labirint de dimensiune <code>N x N</code>, format din camere de dimensiune <code>1 x 1</code>, 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ă:

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

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

= 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 <code>M</code> 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 <code>2</code>, în ordinea în care acestea apar în fișierul de intrare.

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

= Date de ieșire =
Fișierul de ieșire <code>episodul3OUT.txt</code> va conține pe fiecare linie rezultatele operațiilor de tipul <code>2</code>, î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 =

* <code>1 ≤ N ≤ 1000</code>
* <code>1 ≤ M ≤ 250.000</code>
* <code>1 ≤ x, y ≤ N</code>
* pentru operațiile de tipul <code>1</code>: camera <code>(x, y)</code> 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: =
<code>episodul3IN.txt</code>
 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
<code>episodul3OUT.txt</code>
 2
 3
 3

= Exemplul 2: =
<code>episodul3IN.txt</code>
 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
<code>episodul3OUT.txt</code>
 Datele nu corespund restrictiilor impuse
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line="1">
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()

</syntaxhighlight>