0883 - Traversare

Cerința

Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu n linii și m coloane, formată din n*m zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană.

Un călător dorește să traverseze deșertul de la nord (prima linie) la sud (ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesibilă de pe prima line și dorește să ajungă pe ultima linie cu număr minim de pași.

Date de intrare

Fișierul de intrare traversarein.txt conține pe prima linie numerele n m. Următoarele n linii conțin câte m valori 0 sau 1, separate prin câte un spațiu. Valoarea 0 reprezintă o zonă accesibilă, iar valoarea 1 reprezintă o zonă inaccesibilă.

Date de ieșire

Fișierul de ieșire traversareout.txt va conține pe prima linie numărul C, reprezentând numărul minim de pași necesari pentru traversare.

Restricții și precizări

• 1 ≤ n, m ≤ 1000
• în traversarea deșertului un pas este trecerea dintr-o zonă accesibilă în altă zonă accesibilă învecinată cu prima
• la determinarea numărului de pași se numără și primul pas (intrarea în matrice)
• pentru toate datele de test este posibilă traversarea deșertului

Exemplul 1:

traversarein.txt

6 9
1 1 0 0 1 1 1 0 0 
0 0 1 0 1 0 1 1 0 
1 1 0 0 0 0 0 0 0 
1 0 0 0 1 0 0 0 1 
1 0 1 1 0 1 0 0 0 
1 0 0 0 0 0 0 1 0 

traversareout.txt

Datele de intrare corespund restrictiilor impuse
8

Exemplul 2:

traversarein.txt

traversare

traversareout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

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

from collections import deque

def citire_matrice(n_linii, fisier):

   matrix = []
   for i in range(n_linii):
       linie = list(map(int, fisier.readline().split()))
       matrix.append(linie)
   return matrix

def validare_matrice(matrix, n_linii, m_coloane, fisier_out):

   if n_linii > 1000 or m_coloane > 1000:
       raise ValueError
   for linie in matrix:
       for valoare in linie:
           if valoare not in [0, 1]:
               raise ValueError
   fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")

def traversare_desert(matrix, n_linii, m_coloane):

   dx = [-1, 0, 1, 0]
   dy = [0, 1, 0, -1]
   distanta = [[float('inf')] * m_coloane for _ in range(n_linii)]
   q = deque()

   for j in range(m_coloane):
       if matrix[0][j] == 0:
           distanta[0][j] = 1
           q.append((0, j))

   while q:
       x, y = q.popleft()
       for d in range(4):
           nx, ny = x + dx[d], y + dy[d]
           if 0 <= nx < n_linii and 0 <= ny < m_coloane and matrix[nx][ny] == 0:
               if distanta[nx][ny] > distanta[x][y] + 1:
                   distanta[nx][ny] = distanta[x][y] + 1
                   q.append((nx, ny))

   return min(distanta[-1])

if __name__ == '__main__':

   file_in = open("traversarein.txt", "r")
   file_out = open("traversareout.txt", "w")
   try:
       n, m = map(int, file_in.readline().split())
       matrice = citire_matrice(n, file_in)  # modificarea este aici
       validare_matrice(matrice, n, m, file_out)
       rezultat = traversare_desert(matrice, n, m)
       file_out.write(str(rezultat))
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

Explicație

O traversare cu 8 pași a deșertului este următoarea:

1	1	0	0	1	1	1	0	0
0	0	1	0	1	0	1	1	0
1	1	0	0	0	0	0	0	0
1	0	0	0	1	0	0	0	1
1	0	1	1	0	1	0	0	0
1	0	0	0	0	0	0	1	0