Editing 1187 - Roboti 1 (section)

== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import deque


def citire_date_intrare(fisier_intrare):
    with open(fisier_intrare, "r") as f:
        p = int(f.readline().strip())
        n, m, l = map(int, f.readline().strip().split())
        copaci = []
        for _ in range(l):
            x, y = map(int, f.readline().strip().split())
            copaci.append((x - 1, y - 1))  # Corectăm indexarea la 0
        if p == 2:
            Q = int(f.readline().strip())
            k = list(map(int, f.readline().strip().split()))
        else:
            Q = 0
            k = []
    return p, n, m, l, copaci, Q, k


def bfs(n, m, copaci, latura):
    def in_bounds(x, y):
        return 0 <= x < n and 0 <= y < m

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    vizitat = [[False] * m for _ in range(n)]
    for x, y in copaci:
        vizitat[x][y] = True

    num_roboți = 0
    for i in range(n):
        for j in range(m):
            if not vizitat[i][j]:
                num_roboți += 1
                q = deque([(i, j)])
                vizitat[i][j] = True
                while q:
                    x, y = q.popleft()
                    for d in range(4):
                        for k in range(1, latura + 1):
                            nx, ny = x + dx[d] * k, y + dy[d] * k
                            if in_bounds(nx, ny) and not vizitat[nx][ny]:
                                vizitat[nx][ny] = True
                                q.append((nx, ny))
    return num_roboți


def defrisare_minima(n, m, copaci, max_roboți):
    def numar_roboți(latura):
        return bfs(n, m, copaci, latura)

    stanga, dreapta = 1, min(n, m)
    while stanga < dreapta:
        mijloc = (stanga + dreapta) // 2
        if numar_roboți(mijloc) <= max_roboți:
            dreapta = mijloc
        else:
            stanga = mijloc + 1
    return stanga


def latura_minima_robot(n, m, copaci, Q, k):
    rezultate = []
    for fiecare_k in k:
        rezultate.append(defrisare_minima(n, m, copaci, fiecare_k))
    return rezultate


def scrie_rezultate(fisier_iesire, rezultate):
    with open(fisier_iesire, "w") as f:
        for rezultat in rezultate:
            f.write(f"{rezultat}\n")


def main():
    fisier_intrare = "roboti.in"
    fisier_iesire = "roboti.out"

    p, n, m, l, copaci, Q, k = citire_date_intrare(fisier_intrare)

    # Restricții și precizări
    assert 2 <= n <= 150, "n trebuie să fie între 2 și 150"
    assert 2 <= m <= 150, "m trebuie să fie între 2 și 150"
    assert 1 <= l <= 150, "l trebuie să fie între 1 și 150"
    for x, y in copaci:
        assert 0 <= x < n, "Coordonata x trebuie să fie între 1 și n"
        assert 0 <= y < m, "Coordonata y trebuie să fie între 1 și m"
    if p == 2:
        assert 1 <= Q <= 1000, "Q trebuie să fie între 1 și 1000"
        for fiecare_k in k:
            assert 1 <= fiecare_k <= 150, "k[i] trebuie să fie între 1 și 150"

    if p == 1:
        num_roboți = defrisare_minima(n, m, copaci, l)
        rezultate = [num_roboți]
    elif p == 2:
        laturi_minime = latura_minima_robot(n, m, copaci, Q, k)
        rezultate = laturi_minime

    scrie_rezultate(fisier_iesire, rezultate)


if __name__ == "__main__":
    main()

</syntaxhighlight>