3277 - Lee

From Bitnami MediaWiki
Revision as of 16:38, 10 December 2023 by Bonte Lucas Gabriel (talk | contribs) (Pagină nouă: 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 ma...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

  • 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:[edit | edit source]

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:[edit | edit source]

Intrare

lee

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare[edit | edit source]

<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>

Explicație[edit | edit source]

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.