3277 - Lee

Se consideră o matrice cu N linii și N coloane, numerotate de la 1 la N, care memorează doar valori 0 și 1. Se dau de asemenea coordonatele a trei componente din această matrice.

Cerința

Să se determine lungimea minimă a unui drum care pleacă din poziția (1,1), trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția (N, N), drum care trece doar prin componente marcate cu 0 și învecinate pe linii și coloane. Un pas din drum constă din deplasarea dintr-un punct (i,j) într-unul din cele patru învecinate pe linie și coloană, adică într-unul din punctele (i-1,j), (i,j-1), (i+1, j), (i,j+1).

Date de intrare

Programul citește de la tastatură numărul N. Pe fiecare din următoarele N linii și N coloane este descrisă matricea binară. Pe ultimele trei linii sunt câte două numere naturale de forma x y ce descriu coordonatele în matrice (linie și coloană) ale celor trei puncte.

Date de ieșire

Programul va afișa pe ecran un singur număr natural, care reprezintă lungimea minimă a drumului care pornește din (1, 1), trece prin cele trei puncte date și ajunge în punctul (N, N).

Restricții și precizări

• 3 ≤ N ≤ 100
• Cele trei puncte sunt distincte, diferite de pozițiile (1,1) și (N,N) și se găsesc la poziții din matrice marcate cu 0. De asemenea, la pozițiile (1,1) și (N,N) se găsește mereu valoarea 0.
• Pentru datele de intrare va exista mereu soluție, adică există cel puțin un drum de la (1,1) la (N,N).

Exemplul 1:

Intrare

4
0 0 0 0
1 0 1 1
0 0 0 1
1 0 0 0
3 3
1 4
3 1

Ieșire

Datele de intrare corespund restrictiilor impuse.
12

Exemplul 2:

Intrare

lee

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

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

Explicație

Cele trei puncte sunt situate în coordonatele (3,3), (1,4), (3,1). Drumul de lungime minimă este:

de la (1,1) la (1,4) (lungime 3) de la (1,4) la (3,1) (lungime 5) de la (3,1) la (3,3) (lungime 2) de la (3,3) la (4,4) (lungime 2) Lungime totală: 3 + 5 + 2 + 2 = 12.