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