3341 - oaste2

Pe un continent reprezentat printr-o matrice cu n linii și m coloane se află mai multe state, toate în conflict. Astfel, fiecare si-a mobilizat oastea. Fiecare element al matricei reprezintă o regiune.

Două elemente, din matrice, învecinate pe linie sau pe coloană (nu si pe diagonală) reprezintă două regiuni care aparțin aceluiași stat.

Un element din matrice ce contine cifra 0 este o regiune neutră care delimitează statele si nu are soldați.

Elementul ce conține o cifră c nenulă este o regiune ce aparține unui stat și are c soldați.

Cerința

Să se determine numărul S maxim de soldați dintr-un stat al continentului precum și numărul R minim de regiuni pe care le poate avea un stat cu S soldati.

Date de intrare

Fișierul de intrare oaste2.in conține pe prima linie numerele naturale n si m, iar pe fiecare dintre următoarele n linii conține câte m cifre, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire oaste2.out va conține pe prima linie cele două numere S R separate printr-un spațiu, cu semnificația din enunț

Restricții și precizări

• n si m vor fi numere naturale cu valori intre 1 si 100 inclusiv;
• fiecare element al matricei va avea valori naturale cuprinse intre 0 si 9 inclusiv;
• există cel puțin o cifră nenula în matrice

Exemplu:

oaste2.in

4 6
0 1 1 0 2 9
9 0 2 0 1 0
0 1 1 0 0 2
0 0 1 1 1 1

oaste2.out

12 3

Explicație

Harta din fișierul de intrare contine 3 state având: 12 soldați (culoarea rosu – 10 regiuni), 12 soldați (culoare galben – 3 regiuni), 9 soldați (culoare verde – 1 regiune)

<syntaxhighlight lang="python" line="1"> def in_bounds(x, y, n, m):

   return 0 <= x < n and 0 <= y < m

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

   stack = [(x, y)]
   visited[x][y] = True
   soldiers_sum = 0
   region_size = 0
   directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   state_value = matrix[x][y]
   
   while stack:
       cx, cy = stack.pop()
       soldiers_sum += matrix[cx][cy]
       region_size += 1
       
       for dx, dy in directions:
           nx, ny = cx + dx, cy + dy
           if in_bounds(nx, ny, n, m) and not visited[nx][ny] and matrix[nx][ny] == state_value:
               visited[nx][ny] = True
               stack.append((nx, ny))
   
   return soldiers_sum, region_size

def find_strongest_state(matrix):

   n = len(matrix)
   m = len(matrix[0])
   visited = [[False] * m for _ in range(n)]
   
   max_soldiers = 0
   min_regions = float('inf')
   
   for i in range(n):
       for j in range(m):
           if matrix[i][j] != 0 and not visited[i][j]:
               soldiers, regions = dfs(matrix, visited, i, j, n, m)
               if soldiers > max_soldiers:
                   max_soldiers = soldiers
                   min_regions = regions
               elif soldiers == max_soldiers:
                   min_regions = min(min_regions, regions)
   
   return max_soldiers, min_regions

1. Exemplu de utilizare:

matrix = [

   [1, 1, 0, 3],
   [1, 0, 3, 3],
   [2, 2, 2, 0],
   [2, 0, 0, 0]

]

max_soldiers, min_regions = find_strongest_state(matrix) print(f"Număr maxim de soldați: {max_soldiers}, Număr minim de regiuni: {min_regions}") </syntaxhighlight>