0837 - Fill

Cerința

Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unei planete, în care 1 înseamnă uscat, iar 0 înseamnă apă. Două elemente 1 care se învecinează pe linie sau pe coloană (nu și pe diagonală) fac parte din același continent.

Să se determine câte continente sunt pe hartă.

Date de intrare

Fișierul de intrare fill.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau 1, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire fill.out va conține pe prima linie numărul C de continente existente.

Restricții și precizări

• 1 ≤ n , m ≤ 100

Exemplu

Intrare:

fill.in

4 6

1 1 1 0 1 0

0 0 1 0 1 1

1 1 1 0 0 0

0 1 0 1 1 1

Iesire:

fill.out

3

Rezolvare

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

def validare(n, m, harta):

   if len(harta) != n:
       return False
   for linie in harta:
       if len(linie) != m:
           return False
       for element in linie:
           if element != 0 and element != 1:
               return False
   return True

def numar_continente(n, m, harta):

   visited = [[False for j in range(m)] for i in range(n)]
   count = 0
   for i in range(n):
       for j in range(m):
           if harta[i][j] == 1 and not visited[i][j]:
               count += 1
               dfs(i, j, n, m, harta, visited)
   return count

def dfs(x, y, n, m, harta, visited):

   if x < 0 or x >= n or y < 0 or y >= m or visited[x][y] or harta[x][y] == 0:
       return
   visited[x][y] = True
   dfs(x-1, y, n, m, harta, visited)
   dfs(x+1, y, n, m, harta, visited)
   dfs(x, y-1, n, m, harta, visited)
   dfs(x, y+1, n, m, harta, visited)

def main():

   with open("fill.in") as f:
       n, m = map(int, f.readline().split())
       harta = [list(map(int, f.readline().split())) for i in range(n)]

   if not validare(n, m, harta):
       print("Date invalide")
       return

   with open("fill.out", "w") as f:
       f.write(str(numar_continente(n, m, harta)))

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicații

Pentru a rezolva această problemă, putem folosi o variantă a algoritmului DFS (Depth-First Search) pentru a parcurge matricea. Pentru a număra continentele, vom căuta primul element 1 din matrice și vom căuta toate celulele adiacente cu acestea, marcate cu 1, folosind o căutare în adâncime.

1. 1 În implementarea noastră, definim o funcție validare_matrice care verifică dacă matricea introdusă în fișierul de intrare este validă, adică are dimensiunile n și m, și are elemente doar 0 sau 1. În caz contrar, programul va afișa un mesaj de eroare.

1. 2 Funcția rezolva primește matricea și dimensiunile acesteia și returnează numărul de continente găsite. Algoritmul DFS este implementat în funcția auxiliară dfs, care primește matricea, poziția curentă și o matrice booleană care urmărește celulele deja vizitate. Algoritmul parcurge matricea în profunzime și marchează celulele vizitate.

1. 3 În funcția main citim dimensiunile matricei și matricea din fișierul de intrare. Apoi, verificăm dacă matricea este validă. Dacă este validă, apelăm funcția rezolva și afișăm rezultatul în fișierul de ieșire. În caz contrar, afișăm un mesaj de eroare.

Observăm că, pentru a urmări celulele vizitate în matricea de intrare, folosim o matrice suplimentară visited de dimensiune n x m, care conține valori booleane. Aceasta este utilă pentru a evita parcurgerea acelorași celule de mai multe ori.