Oros Ioana Diana at 13:17, 18 May 2024

2024-05-18T13:17:15Z

← Older revision		Revision as of 13:17, 18 May 2024
Line 50:		Line 50:
	2 1 1 2 2		2 1 1 2 2
	<code>episodul3OUT.txt</code>		<code>episodul3OUT.txt</code>
	2		Datele nu corespund restrictiilor impuse
	3
	3
	<br>		<br>
	== Rezolvare ==		== Rezolvare ==

Oros Ioana Diana at 13:16, 18 May 2024

2024-05-18T13:16:36Z

Show changes

Oros Ioana Diana: Pagină nouă: == 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ă...

2024-01-08T21:37:32Z

Pagină nouă: == 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ă. <br> 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ă...

New page

== 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ă.
<br>
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.
== 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
<br>
== Exemplul 2 ==
; episodul3in.txt
: 4 6
: 1 1 1
: 1 1 2
: 1 1 3
: 2 1 1 3 3
: 1 2 2
: 2 1 2 2 2
; episodul3out.txt
: 2
: 1
: 3
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2163 - Episodul 3
from collections import deque

def bfs(start, end, accessible):
queue = deque([(start, 0)])
visited = set()

while queue:
current, steps = queue.popleft()
x, y = current

if current == end:
return steps

if current in visited:
continue

visited.add(current)

for neighbor in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 1 <= neighbor[0] <= N and 1 <= neighbor[1] <= N and neighbor in accessible:
queue.append((neighbor, steps + 1))

return -1 # If no path is found

# Citire date de intrare
try:
with open("episodul3in.txt", "r") as file:
N, M = map(int, file.readline().split())
accessible = set()
result = []

for _ in range(M):
operation = list(map(int, file.readline().split()))

if operation[0] == 1:
accessible.add((operation[1], operation[2]))
elif operation[0] == 2:
if (operation[1], operation[2]) not in accessible or (operation[3], operation[4]) not in accessible:
result.append("Fals")
else:
result.append(bfs((operation[1], operation[2]), (operation[3], operation[4]), accessible))

except Exception as e:
result = ["Fals"]

# Scriere rezultat în fișier de ieșire
with open("episodul3out.txt", "w") as file:
for r in result:
file.write(str(r) + "\n")

</syntaxhighlight>

2163 - Episodul 3 - Revision history

Oros Ioana Diana at 13:17, 18 May 2024

Oros Ioana Diana at 13:16, 18 May 2024