Editing 3277 - Lee (section)

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from heapq import heappop, heappush
from itertools import permutations


def verificare_restrictii(n):  # functia de verificare a datelor de intrare
    if 3 <= n <= 100:
        return True
    else:
        return False


def distanta_minima(matrice, start, end):
    n = len(matrice)
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    distante = [[float('inf')] * n for _ in range(n)]
    distante[start[0]][start[1]] = 0
    heap = [(0, start)]
    while heap:
        d, (x, y) = heappop(heap)
        if (x, y) == end:
            return d
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and matrice[nx][ny] == 0:
                if d + 1 < distante[nx][ny]:
                    distante[nx][ny] = d + 1
                    heappush(heap, (d + 1, (nx, ny)))
    return float('inf')


def rezolvare():
    n = int(input("Introduceti dimensiunea matricei (un numar natural): "))
    if not verificare_restrictii(n):
        print("Datele de intrare nu corespund restrictiilor impuse.")
        return
    print("Datele de intrare corespund restrictiilor impuse.")
    print("Introduceti matricea linie cu linie (0 sau 1 separate prin spatii): ")
    matrice = [list(map(int, input().split())) for _ in range(n)]
    puncte = [(0, 0)]
    print("Introduceti coordonatele celor trei puncte (doua numere naturale separate prin spatii): ")
    for _ in range(3):
        x, y = map(int, input().split())
        puncte.append((x - 1, y - 1))
    puncte.append((n - 1, n - 1))
    distante = [[distanta_minima(matrice, puncte[i], puncte[j]) for j in range(5)] for i in range(5)]
    min_distanta = float('inf')
    for perm in permutations([1, 2, 3]):
        distanta = distante[0][perm[0]] + distante[perm[0]][perm[1]] + distante[perm[1]][perm[2]] + distante[perm[2]][4]
        min_distanta = min(min_distanta, distanta)
    print("Lungimea minima a drumului este: ", min_distanta)


if __name__ == '__main__':
    try:
        rezolvare()
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse.")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>