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.

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

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

Rezolvare

#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")